---
abstract: 'In this paper, we introduce a discrete variant of the meta-learning framework. Meta-learning aims at exploiting prior experience and data to improve performance on future tasks. By now, there exist numerous formulations for meta-learning in the continuous domain. Notably, the Model-Agnostic Meta-Learning (MAML) formulation views each task as a continuous optimization problem and based on prior data learns a suitable initialization that can be adapted to new, unseen tasks after a few simple gradient updates. Motivated by this terminology, we propose a novel meta-learning framework in the discrete domain where each task is equivalent to maximizing a set function under a cardinality constraint. Our approach aims at using prior data, i.e., previously visited tasks, to train a proper initial solution set that can be quickly adapted to a new task at a relatively low computational cost. This approach leads to (i) a personalized solution for each individual task, and (ii) significantly reduced computational cost at test time compared to the case where the solution is fully optimized once the new task is revealed. The training procedure is performed by solving a challenging discrete optimization problem for which we present deterministic and randomized algorithms. In the case where the tasks are monotone and submodular, we show strong theoretical guarantees for our proposed methods even though the training objective may not be submodular. We also demonstrate the effectiveness of our framework on two real-world problem instances where we observe that our methods lead to a significant reduction in computational complexity in solving the new tasks while incurring a small performance loss compared to when the tasks are fully optimized.'
author:
- 'Arman Adibi[^1] ,Aryan Mokhtari[^2] ,Hamed Hassani[^3]'
bibliography:
- 'ref.bib'
- 'ref\_2.bib'
title: ' Submodular Meta-Learning '
---

Introduction
============

Many applications in artificial intelligence necessitate exploiting prior data and experience to enhance quality and efficiency on new tasks. This is often manifested through a set of tasks given in the training phase from which we can learn a model or representation that can be later used for new unseen tasks in the test phase. In this regard, meta-learning aims at exploiting the data from the available tasks to learn model parameters or representation that can be later used to perform well on new unseen tasks, in particular, when we have access to limited data and computational power at the test time [@thrun2012learning; @schmidhuber1992learning; @bengio1990learning; @vilalta2002perspective]. By now, there are several formulations for meta-learning, but perhaps one of the most successful ones is the Model-Agnostic Meta-Learning (MAML) framework proposed in [@finn2017model]. In MAML, we aim to train the model parameters such that applying a few steps of gradient-based updates with a small number of samples from a new task would perform well on that task. MAML can also be viewed as a way to provide a proper initialization, from which performance on a new task can be optimized after a few gradient-based updates. Alas, this scheme only applies to settings in which the decision variable belongs to a *continuous* domain and can be adjusted using gradient-based methods at the test time.

Our goal is to extend the methodology of MAML to the *discrete* setting. We consider a setting in which our decision variable is a discrete set, and our goal is to come up with a good initial set that can be quickly adjusted to perform well over a wide range of new tasks. In particular, we focus on submodular maximization to represent the tasks which is an essential class of discrete optimization.

There are numerous applications where the submodular meta-learning framework can be applied to find a personalized solution for each task while significantly reducing the computation load. In general, most recommendation tasks can be cast as an instance of this setting[@gabillon2013adaptive; @el2009turning; @yue2011linear]. Consider the task of recommending a set of items, e.g., products, locations, ads, to a set of users. One approach for solving such a problem is to find the subset of items that have the highest score over all the previously-visited users and recommend that subset to a new user. Indeed, this approach leads to a reasonable performance at test time; however, it does not provide a user-specific solution for a new user. Another approach is to find the whole subset at the test time when the new user arrives. In contrast to the previous approach, this scheme leads to a user-specific solution, but at the cost of running a computationally expensive algorithm to select all the elements at the test time.

In our meta-learning framework, the process of selecting set items to be recommended to a new user is done in two parts: In the first part, a set of items is selected offline according to prior experience. These items are the most popular items to the previously-visited users (depending on the context). In the second part, which happens at the test time, a set of items that is *personalized* to the coming user is selected. These are items that are computed specifically according to the features of the coming user. In this manner, the computation for each coming user would be reduced to the selection of the second part, which typically constitutes a small portion of the final set of recommended items. The first part can be done offline with a lower frequency. For instance, in a real recommender system, the first part can be computed once every hour, and the second part can be computed specifically for each coming user (or for a class of similar users). While we have mentioned recommendation (or more generally facility location) as a specific example, it is easy to see that this framework can be easily used to reduce computation in other notable applications of submodular optimization. **Contributions.** Our contributions are threefold:

-   We propose a novel discrete meta-learning framework where each task is equivalent to maximizing a set function under some cardinality constraint. Our framework aims at using prior data, i.e., previously visited tasks, to train a proper initial solution set that can be quickly adapted to a new task at a low computational cost to obtain a task-specific solution.

-   We present computationally efficient deterministic and randomized meta-greedy algorithms to solve the resulting meta-learning problem. When the tasks are monotone and submodular, we prove that the solution obtained by the deterministic algorithm is at least $0.53$-optimal, and the solution of the randomized algorithm is $(1-1/e-o(1))$-optimal in expectation, where the $o(1)$ term vanishes by the size of the solution. These guarantees are obtained by introducing new techniques, despite that the meta-learning objective is *not* submodular.

-   We study the performance of our proposed meta-learning framework and algorithms for movie recommendation and ride-sharing problems. Our experiments illustrate that the solution of our proposed meta-learning scheme, which chooses a large portion of the solution in the training phase and a small portion adaptively at test time, is very close to the solution obtained by choosing the entire solution at the test time when a new task is revealed.

Related work
------------

**Continuous Meta-Learning.** Meta-learning has gained considerable attention recently mainly due to its success in few shot learning [@vinyals2016matching; @DBLP:conf/iclr/RaviL17; @snell2017prototypical; @wang2019few] as well as reinforcement learning [@DBLP:journals/corr/DuanSCBSA16; @wang2016learning; @DBLP:conf/iclr/SongGYCPT20; @fallah2020provably]. One of the most successful forms of meta-learning is the gradient-based *Model Agnostic Meta-learning* (MAML) approach[@finn2017model]. MAML aims at learning an initialization that can be adapted to a new task after performing one (or a few) gradient-based update(s); see, e.g., [@fallah2019convergence]. This problem can be written as $$\min_{w \in W} \mathbb{E}_{a\sim P}[f_a(w-\nabla f_a(w))],$$ where $W \subseteq \mathbb{R}^d$ is the feasible set and $l$ is the probability distribution over tasks. The previous works on MAML including [@nichol2018first; @finn2018probabilistic; @DBLP:conf/iclr/GrantFLDG18; @yoon2018bayesian; @DBLP:conf/iclr/AntoniouES19; @rajeswaran2019meta; @fallah2019convergence; @collins2020distribution] consider the case where $W$ is a continuous space. In fact none of these works can be applied to the case where the feasible parameter space is discrete. In this paper, we aim to close this gap and extend the terminology of MAML to discrete settings.

**Submodular Maximization.** Submodular functions have become key concepts in numerous applications such as data summarization [@lin2011class; @wei2013using; @kirchhoff2014submodularity; @mirzasoleiman2016distributed], viral marketing [@kempe2003maximizing], sensor placement [@krause2008near], dictionary learning [@das2011submodular], and influence maximization [@kempe2003maximizing]. It is well-known that for maximizing a monotone and submodular function under the cardinality constraint, the greedy algorithm provides a $(1-1/e)$-optimal solution [@krause2014submodular; @nemhauser1978best; @wolsey1982analysis]. There has been significant effort to improve the scalability and efficiency of the greedy algorithm using lazy, stochastic, and distributed methods [@mirzasoleiman2015lazier; @karimi2017stochastic; @barbosa2015power; @mirrokni2015randomized; @kumar2015fast; @hassani2017gradient; @mokhtari2020stochastic; @karbasi2019stochastic; @balkanski2019exponential]. However, our framework is fundamentally different and complementary to these approaches as it proposes a new approach to use data at training time to improve performance at new tasks. Indeed, all the aforementioned techniques can be readily used to further speed-up our algorithms. Optimization of related submodular tasks has been a well-studied problem with works on structured prediction [@lin2012learning], submodular bandits [@yue2011linear; @zhang2019online], online submodular optimization [@jegelka2011online; @streeter2009online; @golovin2014online; @chen2018projection], and public-private data summarization [@mirzasoleiman2016fast]. However, unlike our work, these approaches are not concerned with train-test phases for optimization. Another recently-developed methodology to reduce computation is the two-stage submodular optimization framework [@balkanski2016learning; @mitrovic2018data; @stan2017probabilistic], which aims at summarizing the ground set to a reasonably small set that can be used at test time. The main difference of our framework with the two-stage approaches is that we allow for *personalization*: A small subset of items that can be found at test time specific to the task at hand. This leads to a completely new problem formulation, and consequently, new algorithms.

Problem Statement: Discrete Meta-Learning {#sect:prob-statement}
=========================================

**Setup.** We consider a family of tasks $\mathcal{T}=\{\mathcal{T}_i\}_{i\in \mathcal{I}}$, where the set $\mathcal{I}$ could be of infinite size. Each task $\mathcal{T}_i$ is represented via a set function $f_i:2^{V} \to {\mathbb{R}}_+$ that measures the reward of a set $S \subseteq V $ for the $i$-th task, and performing the task $\mathcal{T}_i$ would mean to maximize the function $f_i$ subject to a given constraint. For instance, in a recommender system where we aim to recommend a subset of the items to the users, the set $\mathcal{I}$ denotes the set of all the possible users and selecting which items to recommend to a user $i \in \mathcal{I}$ is viewed as the task $\mathcal{T}_i$. Moreover, the function $f_i$ encodes the users satisfaction, i.e., $f_i(S)$ quantifies how suitable the set of items $S$ is for user $i$. Taking a statistical perspective, we assume that the tasks $\mathcal{T}_i$ occur according to a possibly unknown probability distribution $i \sim p$.

In this paper, we focus on the case where the functions $f_i$ are monotone and submodular set functions and each task $\mathcal{T}_i$ amounts to maximizing $f_i$ under the $k$-cardinality constraint. That is, the task $\mathcal{T}_i$ is to select a subset $S \subseteq V$ of size $k$ such that the value of $f_i(S)$ is maximized. Submodularity of $f_i$ means that for any $A,B \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 should directly optimize $f_{\rm{test}}$ by solving the following problem $$\label{test_problem}
    \max_{S\in V, |S|\leq k}\  f_{\rm{test}}(S).$$ We denote the optimal solution of by $S_{\rm test}^*$. For instance, we can use the greedy procedure to solve  which leads to a $(1-1/e)$-optimal solution using $\mathcal{O}(kn)$ evaluations of $f_{\rm test}$, and through $k$ passes over the ground set. However, the available computational power and time in the test phase is often limited, either because we need to make quick decisions to respond to new users or since we need to save energy. For instance, in real-world advertising or recommendation systems, both these requirements are crucial: many users arrive within each hour which means fast optimization is crucial (especially if $n,k$ are large), and also, reducing computation load would lead to huge energy savings in the long run. In such cases, Problem  should be solved approximately with less computation.

An alternative to reduce computation at test time is to solve the problem associated with the expected reward over all possible tasks in the training phase (when we have sufficient computation time), i.e., $$\label{expected_max}
    \max_{S\in V, |S|\leq k} \ \mathbb{E}_{i \sim p}\; [f_i(S)].$$ We denote the optimal solution of by $S_{\rm exp}^*$. The rationale behind this approach is that the optimal solution to this problem would generalize well over an unseen task if the new task is also drawn according to the probability distribution $p$. In other words, the solution of should perform well for the problem in that we aim to solve at the test time, assuming that $f_{\rm test}$ is sampled according to $p$. In this way, we do not need any extra computation at the test time. However, in this case, the solution that we obtain would not be the best possible solution for the task that we observe at the test time, i.e., $S_{\rm test}^*$ is not equal to $S_{\rm exp}^*$. Note that we often do not have access to the underlying probability distribution $p$, and we only have access to a large set of realizations of tasks in the training phase. As a result, instead of solving , we settle for maximizing the sample average function $$\label{empirical_max}
    \max_{S\in V, |S|\leq k} \ \frac{1}{m}\sum_{i=1}^m f_i(S),$$ where $m$ is the number of available tasks in the training phase.

Problems and can be considered as two different extreme cases. In the first option, by solving , we avoid any pre-processing in the training phase, 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 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 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 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 and how can the functions $f_i$ be incorporated in finding the right order, which is the main challenge in designing greedy methods to solve . We design greedy procedures with both deterministic and randomized orders and provide strong guarantees for their solutions.

Deterministic Algorithms
------------------------

In this section, we first describe Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] which use specific orderings to solve Problem . Based on these two, we then design Algorithm \[alg: main discrete meta-Greedy\] as our *main deterministic* algorithm. Throughout this section, we use $\Delta_i(e|S)=f_i(S\cup\{e\})-f_i(S)$ to denote the marginal gain of adding an element $e$ to set $S$ for function $f_i$. In brief, Algorithm \[alg: discrete meta-Greedy\] first fills ${S_{\rm{tr}}}$ greedily up to completion and then it constructs each of the $S_i$’s greedily on the top of ${S_{\rm{tr}}}$. Specifically, starting from the empty set initialization for ${S_{\rm{tr}}}$ and $S_i$’s, Algorithm \[alg: discrete meta-Greedy\] constructs in its first phase the set ${S_{\rm{tr}}}$ in $l$ rounds, by adding one element per round, where the next element in each round is chosen according to $ e^* = \operatorname*{arg\,max}_{e \in V} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup \{e\}) - f_{i}({S_{\rm{tr}}})$. Once ${S_{\rm{tr}}}$ is completed, in the second phase, each of the sets $S_i$ is constructed in parallel by running the greedy algorithm on $f_i$. That is, each $S_i$ is updated in $k-l$ rounds where in each round an element with maximum marginal on $f_i$ is added to $S_i$ based on $ e^*_i = \operatorname*{arg\,max}_{e \in V} f_i({S_{\rm{tr}}}\cup S_i \cup\{e\}) - f_i({S_{\rm{tr}}}\cup S_i)$.

**Initialize** ${S_{\rm{tr}}}=\{S_i\}_{i=1}^m=\emptyset$ Find $e^{*}\!\!\! =\!\! \operatorname*{arg\,max}_{ e\in V}\sum\limits_{i=1}^{m}\Delta_i(e|{S_{\rm{tr}}}) $ ${S_{\rm{tr}}}\xleftarrow{} {S_{\rm{tr}}}\cup\{e^{*}\}$ **end for** Find $e_i^{*} \!=\!\operatorname*{arg\,max}_{ e\in V}  \Delta_i(e|{S_{\rm{tr}}}\!\cup\! S_i)$ $S_i\xleftarrow{} S_i\cup\{e_i^{*}\}$ **end for** **end for** Return ${S_{\rm{tr}}}$ and $S_i$

**Initialize** ${S_{\rm{tr}}}=\{S_i\}_{i=1}^m=\emptyset$ Find $e_i^{*} =  \operatorname*{arg\,max}_{ e\in V}  \Delta_i(e|S_i)$ $S_i\xleftarrow{} S_i\cup\{e_i^{*}\}$ **end for** **end for** Find $ e^{*} =\!\operatorname*{arg\,max}_{ e\in V} \!\sum\limits_{i=1}^{m}\!\Delta_{i}(e|{S_{\rm{tr}}}\cup S_i)$ ${S_{\rm{tr}}}\xleftarrow{} {S_{\rm{tr}}}\cup\{e^{*}\}$ **end for** Return ${S_{\rm{tr}}}$ and $S_i$

**Initialize** the sets ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$ to the empty set. Find $e^{*} = \operatorname*{arg\,max}_{ e\in V}  \sum_{i=1}^{m}f_i({S_{\rm{tr}}}\cup\{e\})-f_i({S_{\rm{tr}}})$ ${S_{\rm{tr}}}\xleftarrow{} {S_{\rm{tr}}}\cup\{e^{*}\}$ **end for** Find $e_i^{*} =  \operatorname*{arg\,max}_{ e\in V}  f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ $S_i\xleftarrow{} S_i\cup\{e_i^{*}\}$ **end for** **end for** return ${S_{\rm{tr}}}$ and $S_i$

Algorithm \[alg: Reverse discrete meta-Greedy\] uses the opposite ordering of Algorithm \[alg: discrete meta-Greedy\]. Initializing with all sets to be empty, in the first phase it constructs the sets $S_i$ using the greedy procedure on $f_i$, i.e., each $S_i$ is updated in parallel in $k-l$ rounds, where in each round the element $e_i^{*}$ defined as $e_i^{*} =  \operatorname*{arg\,max}_{ e\in V}  f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ is added to $S_i$. In the second phase, the set ${S_{\rm{tr}}}$ is formed greedily in $l$ rounds, and in each round the element $e^{*}  $ defined as $e^{*} =  \operatorname*{arg\,max}_{ e\in V} \sum_{i=1}^{m}f_i({S_{\rm{tr}}}\cup\{e\}\cup S_i)-f_i({S_{\rm{tr}}}\cup S_i)$ is added.

**Initialize** the sets ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$ to the empty set. Find $e_i^{*} =  \operatorname*{arg\,max}_{ e\in V}  f_i(S_i\cup\{e\})-f_i(S_i)$ $S_i\xleftarrow{} S_i\cup\{e_i^{*}\}$ **end for** **end for** Find $e^{*} =  \operatorname*{arg\,max}_{ e\in V} \sum_{i=1}^{m}f_i({S_{\rm{tr}}}\cup\{e\}\cup S_i)-f_i({S_{\rm{tr}}}\cup S_i)$ ${S_{\rm{tr}}}\xleftarrow{} {S_{\rm{tr}}}\cup\{e^{*}\}$ **end for**

return ${S_{\rm{tr}}}$ and $S_i$

While the solutions obtained by Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] are guaranteed to be near-optimal, it turns out that they can be complementary with respect to each other. Our *main* deterministic algorithm, called `Meta-Greedy`, runs both Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] and chooses as output the solution, among the two, that leads to a higher objective value in . To be more specific, if we consider ${S_{\rm{tr}}}^{(1)}, \{S_i^{(1)}\}_{i=1}^m$ as the outputs of Algorithm \[alg: discrete meta-Greedy\] and ${S_{\rm{tr}}}^{(2)}, \{S_i^{(2)}\}_{i=1}^m$ as the outputs of Algorithm \[alg: Reverse discrete meta-Greedy\], then `Meta-Greedy` compares the values of $ \sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{(1)}\cup S_i^{(1)})$ and $ \sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{(2)}\cup S_i^{(2)})$ and chooses the solution set that has the higher objective function value. Note that as we described earlier, the main output of this procedure should be the set ${S_{\rm{tr}}}$ of size $l$. Hence, the output of `Meta-Greedy` is either ${S_{\rm{tr}}}^{(1)}$ or ${S_{\rm{tr}}}^{(2)}$ and the sets $ \{S_i^{(1)}\}_{i=1}^m$ and $ \{S_i^{(2)}\}_{i=1}^m$ are only evaluated for the purpose of comparing objective function values.

Next, we explain why our $\texttt{Meta-Greedy}$ method can outperform both Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\]. This will be done by providing the theoretical guarantees for these methods and consequently explaining why Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] are complementary.

Run Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] and obtain respective solution sets ${S_{\rm{tr}}}^{(1)}, \{S_i^{(1)}\}_{i=1}^m$ and ${S_{\rm{tr}}}^{(2)}, \{S_i^{(2)}\}_{i=1}^m$.

Compute the objective value $ \sum_{i=1}^{m}f_i({S_{\rm{tr}}}\cup S_i)$ for both solution sets.

**Theoretical guarantees.** We begin with the analysis of Algorithm \[alg: discrete meta-Greedy\]. The following proposition relates the overall performance of Algorithm \[alg: discrete meta-Greedy\] to its performance after phase 1 and shows that the output of the algorithm is at least $1/2$-optimal. We use OPT for the optimal value of Problem .

\[alg1lemma\] Let ${S_{\rm{tr}}}^{(1)}, \{S_i^{(1)}\}_{i=1}^m$ be the output of Algorithm \[alg: discrete meta-Greedy\], and define $\beta$ as $\beta :=\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}^{(1)})$. If the set functions $f_i$ are monotone and submodular, then $$\frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)}) 
    \geq \max \Bigl\{ \beta \,, \, (1-1/e)({\rm{OPT}} - 2 \beta) + \beta \Bigr \}.$$ Consequently, the solution obtained by Algorithm \[alg: discrete meta-Greedy\] is at least $1/2$-optimal for any value of $\beta$.

Check Appendix \[sec:proof\_prop\_1\].

The proof of this proposition is relegated to the appendix. The key step in the proof is to relate the progress made in phase 1 to the gap to OPT. This is indeed challenging as phase 1 only involves updates on the outer maximization of . In this regard, we prove a novel technical lemma that can be generally applicable to any mini-max submodular problem. The guarantee given in Proposition \[alg1lemma\] is minimized when $\beta = \text{OPT}/2$. If $\beta$ is small (e.g., $\beta = 0$) or if $\beta$ is large (e.g. if $\beta = (1-1/e)\text{OPT}$) then the guarantee becomes tight (e.g. $(1-1/e)\text{OPT})$. This is indeed expected from the greedy nature of the two phases of Algorithm \[alg: discrete meta-Greedy\]. What is non-trivial about the result of Proposition \[alg1lemma\] is that it provides a strong guarantee for any value of $\beta$, and not just cases that $\beta$ is small or large. Similarly, we can provide near-optimality guarantees for Algorithm \[alg: Reverse discrete meta-Greedy\].

\[alg2lemma\] Let ${S_{\rm{tr}}}^{(2)}, \{S_i^{(2)}\}_{i=1}^m$ be the output of Algorithm \[alg: Reverse discrete meta-Greedy\], and define $\gamma$ as $\gamma := \frac{1}{m}\sum_{i=1}^m f_i(S_i^{(2)})$. If the set functions $f_i$ are monotone and submodular, then $$\frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)}) \geq \max \Bigl\{ \gamma \,, \, (1-1/e)({\rm{OPT}} - 2\gamma) + \gamma \Bigr \}.$$ Consequently, the solution obtained by Algorithm \[alg: Reverse discrete meta-Greedy\] is at least $1/2$-optimal for any value of $\gamma$.

Check Appendix \[sec:proof\_prop\_2\].

Similarly, we can show that $\gamma=\text{OPT}/2$ leads to (the worst) guarantee $1/2$-OPT, while for large and small values of $\gamma$ the bound in Proposition \[alg2lemma\] approaches the optimal approximation $(1-1/e)\text{OPT}$.

We note that the values $\beta$ in Proposition \[alg1lemma\] (Algorithm \[alg: discrete meta-Greedy\]) and $\gamma$ in Proposition \[alg2lemma\] (Algorithm \[alg: Reverse discrete meta-Greedy\]) represent two different extremes. The value $\beta$ represents the significance of the role of ${S_{\rm{tr}}}$ in solving Problem , and $\gamma$ represents how significant the role of the sets $\{S_i\}_{i=1}^m$ can be. Even though the worst-case guarantees of Propositions \[alg1lemma\] and \[alg2lemma\] are obtained when $\beta, \gamma = \text{OPT}/2$, a coupled analysis of the algorithms show that in this case at least one of the algorithms should output a solution which is strictly better than $1/2$-optimal. In other words, the outcomes of Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] are dependent to one another, and the best performance is achieved when the maximum of the two is considered. This justifies why our main algorithm $\texttt{Meta-Greedy}$ can perform strictly better than each of the Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\]. Using a coupled analysis of the outcome of Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\], we can bound the performance of $\texttt{Meta-Greedy}$ for different values of $\beta$ and $\gamma$ (see the proof of Theorem \[thm:meta-greedy\] in the appendix). In particular, we can show that the output of $\texttt{Meta-Greedy}$ is at least $0.53$-optimal. The proof of the following theorem carefully analyzes the interplay between the role of the inner and outer maximization problems in . We emphasize that the proof introduces new techniques applicable to other types of minimax submodular problems.

\[thm:meta-greedy\] Consider the $\texttt{Meta-Greedy}$ algorithm outlined in Algorithm \[alg: main discrete meta-Greedy\]. If the functions $f_i$ are monotone and submodular, then we have $$\label{bound-meta-greedy}
\max \Bigl\{  \frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)}) \, , \, \frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)}) \Bigr\} \geq 0.53 \times {\rm{OPT}}.$$

Check Appendix \[sec:proof\_of\_main\_thm\].

Note that for all the results in Propositions \[alg1lemma\] and \[alg2lemma\] as well as Theorem \[thm:meta-greedy\], for given output sets ${S_{\rm{tr}}}$ or $\{S_i\}_{i=1}^m$, the value of $\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)$ is a lower bound for the objective function value of Problem evaluated at the output set ${S_{\rm{tr}}}$. To be more precise, the accurate measure for evaluating the quality of the output set ${S_{\rm{tr}}}$ is $\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]$ which is indeed larger than $\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)$. Hence, all the guarantees that have obtained in the statements above (as well as Theorem \[thm: randomized meta\] below) would directly translate into the same guarantees when we evaluate the objective in on the set ${S_{\rm{tr}}}$.

Randomized Algorithm
--------------------

In this section, we consider greedy procedures in which the decision to alternate between the set ${S_{\rm{tr}}}$ (the outer maximization) and the sets $\{S_i\}_{i=1}^m$ (the inner maximization) is done based on a randomized scheme. The `Randomized meta-Greedy` procedure, outlined in Algorithm \[alg: Randomized meta-Greedy\], provides a specific randomized order. In each round, with probability $l/k$ we choose to perform a greedy update on ${S_{\rm{tr}}}$, and with probability $1-l/k$ we choose to perform a greedy update on *all* the $S_i$’s, $i=1, \cdots,m$. This procedure continues until either ${S_{\rm{tr}}}$ or $\{S_i\}_{i=1}^m$ hit their corresponding carnality constraint, in which case we continue to update the other set(s) greedily until they also become full.

**Initialize** the sets ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$ to the empty set. $e^{*}_i \xleftarrow{} \operatorname*{arg\,max}_{ e\in V}  f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ $e^{*}_{tr} \xleftarrow{} \operatorname*{arg\,max}_{ e\in V} \sum_{i=1}^{m} f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ **w.p. $\frac{l}{k}$:** ${S_{\rm{tr}}}={S_{\rm{tr}}}\cup\{e^{*}_{tr}\}$ **w.p. $\frac{k-l}{k}$:** $S_i=S_i\cup\{e_i^{*}\}$, $\forall i = 1, \cdots, m$ **end** If ${S_{\rm{tr}}}$ or $S_i$’s have not yet reached their cardinality limit then fill them greedily until their limit is reached Return ${S_{\rm{tr}}}$ and $S_i$

The randomized update of Algorithm \[alg: Randomized meta-Greedy\] is designed to optimally connect the expected increase the objective value at each round with the gap to OPT (as shown in the proof of Theorem \[thm: randomized meta\]). Hence, the `Randomized meta-Greedy` procedure is able to achieve in expectation a guarantee close to the tight value $(1-1/e)\text{OPT}$. However, due to the randomized nature of the algorithm, the sets ${S_{\rm{tr}}}$ or $S_i$ might hit their carnality constraint earlier than expected. Analyzing the function value at this “stopping time” is another technical challenge that we resolve in the following theorem to obtain a guarantee that becomes slightly worse than $(1-1/e)\text{OPT}$ depending on the values of $k-l$ and $l$.

\[thm: randomized meta\] Let the (random) sets ${S_{\rm{tr}}}$, $\{S_i\}_{i=1}^m$ be the output of Algorithm \[alg: Randomized meta-Greedy\]. If the functions $f_i$ are monotone and submodular, then $$\mathbb{E}\Bigl[\frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}\cup S_i) \Bigr] 
\geq \left(1 - \frac{1}{e} - b \right) \rm{OPT},$$ where $b \to 0$ as $k-l$ and $l$ grow. More precisely, letting $c = \max\{\frac{1}{k-l}, \frac{1}{l}\},$ we have $b = c + (\exp(3\sqrt{c\log1/c}) - 1)/e = {\mathcal{O}}(\sqrt{c \log 1/c}).$

Check Appendix \[sec:proof\_of\_main\_random\_theorem\].

All presented algorithms are designed for the training phase and their output is the set ${S_{\rm{tr}}}$ with size $l$. The sets $\{S_i\}_{i=1}^m$ are only computed for algorithmic purposes. Given a new task at the test phase, the remaining $k-l$ task-specific elements will be added to ${S_{\rm{tr}}}$ using for instance greedy updates that require a total complexity of $O((k-l)n)$ in function evaluations. Also, the training complexity of the proposed algorithms is $O(kmn)$, however, certain phases can be implemented in parallel.

Simulation Results {#sec:Simulation}
==================

We provide two experimental setups to evaluate the performance of our proposed algorithms and compare with other baselines. Each setup involves a different set of tasks which are represented as submodular maximization problems subject to the $k$-cardinality constraint. In our experiments, we consider the following algorithms: **Meta-Greedy** (Algorithm \[alg: main discrete meta-Greedy\]), **Randomized Meta-Greedy** (Algorithm \[alg: Randomized meta-Greedy\]), **Greedy-Train** (which chooses all the $k$ elements during the training phase–see and the discussion therein), **Greedy-Test** (which chooses all the $k$ elements during the test phase–see and the discussion therein), and **Random** (which chooses a random set of $k$ elements). In the following, we briefly explain the data and tasks and refer the reader to the supplementary materials for more details.

We described the Meta submodular learning problem and algorithms in previous sections. In this section, we provide two applications:

-   Ride Share Optimization

-   Movie Recommendation

We compare the performance of proposed algorithms on them by showing the comparison in figure\[fig:simulation-ride\].

[0.48]{} ![image](varyl_ridesharewithout2alg.eps){width="1\linewidth"}

[0.48]{} ![image](varyk_ridesharewithout_2alg.eps){width="1\linewidth"}

[0.48]{} ![image](movierecom_varyl_withrand2_without2alg.eps){width="1\linewidth"}

[0.48]{} ![image](movierecom_varyk_withrand2_withoutrandset_without2alg.eps){width="1\linewidth"}

[0.48]{} ![image](movierecom_varyk_withrand.eps){width="1.1\linewidth"}

[0.48]{} ![image](movierecom_varyl_withrand.eps){width="1.1\linewidth"}

**Ride Share Optimization.** We will formalize and solve a facility location problem on the Uber dataset [@uber_2019]. Our experiments were run on the portion of data corresponding to Uber pick-ups in Manhattan in the period of September 2014. This portion consists of $\sim 10^6$ data points each represented as a triplet $(latitude, longitude, DateTime)$. A customer and a driver are specified through their locations on the map. We use $u=(x_u,y_u)$ for a customer a and $r=(x_r, y_r)$ for a driver. We define the “convenience score” of a (customer, driver) pair as $c(u,r)=2-\frac{2}{1+e^{-200 d(u,r)}}$, where $d(u,r)$ denotes the Manhattan distance [@mitrovic2018data]. Given a specific time $a$, we define a time slot $T_a$ and picking inside the data set 10 points in half an hour prior to time $a$, and for each point we further pick 10 points in its 1 km neighborhood, which makes a total of 100 points (locations) on the map. A task ${\mathcal{T}}_i$ takes place at a corresponding time $a_i$, and by defining the set of locations $T_{a_i}$ as above, we let $f_i$ be a monotone submodular function defined over a set $S$ of driver locations as $f_i(S)=\sum_{u\in T_{a_i}}\max_{r\in S}c(u,r)$. We pick 100,000 locations at random from the September 2014 Uber pick-up locations as a ground set. For training we form $m=50$ tasks by picking for each task a random time in the *first* week of Sept. 2014. We test on $m=50$ new tasks formed similarly from the *second* week of Sept. 2014 and report in the figures the average performance obtained at test tasks. Figures \[fig:simulation-1-rideshare\] and \[fig:simulation-2-rideshare\] show the performance of our proposed algorithms against the baselines mentioned above. Figure shows the performance of all algorithms when we fix $k=20$, and vary $l$ from 5 to 18. Larger $l$ means less computation at test time (since we need to further choose $k-l$ elements at test). However, we see that even for large values of $l$ (e.g. $l=16$), the performance of Meta-Greedy is still quite close to the ideal performance of Greedy-Test. Putting this together with the fact that the performance of Greedy-Train is not so good, we can conclude that adding a few personalized elements at test time significantly boosts performance to be even close to the ideal. In Figure , we compare the performance of all the algorithms when $k$ changes from 5 to 30, and $l$ is $80\%$ of $k$ ($l = \lfloor 0.8 k \rfloor$). As we can see, even when we just learn $20\%$ of the set in test time, the performance of Meta-greedy is close to Test-Greedy. Also, when $k-l$ increases, Random-Meta-Greedy performs better than Meta-Greedy. This is in compliance with the results of Theorems \[thm:meta-greedy\], \[thm: randomized meta\].

**Movie Recommendation.** In this application, we use the Movielens dataset [@harper2015movielens] which consists of $10^6$ ratings (from 1 to 5) by $6041$ users for $4000$ movies. We pick the 2000 most rated movies, and 200 users who rated the highest number of movies (similar to [@stan2017probabilistic]). We partitioned the 200 users into 100 users for the training phase and 100 other users for the test phase. Each movie can belong to one of 18 genres. For each genre $t$ we let $G_t$ be the set of all movies with in genre $t$. For each user $i$, we let $R_i$ be the set of all movie rated by the user, and for each movie $v \in R_i$ the corresponding rating is denoted by $r_i(v)$. Furthermore, for user $i$ we define $ f_i(S)=\sum_{t=1}^{18}  w_{i,t}.\max_{v\in R_i\cap G_t \cap S} r_i(v)$ which is the weighted average over maximum rate that user $i$ gives to movies from each genre and $w_{i,t}$ is proportion of movies in genre $t$ which is rated by user $i$ out of all the rating he provides. A task ${\mathcal{T}}_i$ involves 5 users $i_1, \cdots, i_5$ and the function assigned to the task is the average of $f_{i_1}, \cdots, f_{i_5}$. We formed $m=50$ training tasks from the users in the training phase, and $m=50$ test tasks from the users in the test phase. Figure (resp. \[fig:simulation-2-movrecom\]) has been obtained in a similar format as Figure \[fig:simulation-1-rideshare\] (resp. Figure \[fig:simulation-2-rideshare\]). We observe a very similar pattern as in the ride share experiments.

![Comparison of two-stage framework and submodular meta-learning framework []{data-label="fig:twostage"}](rideshare_twostage.eps){width="8cm"}

Comparison with Two-stage Submodular Optimization {#sec:two_stage}
=================================================

Two-stage submodular optimization is another way to deal with limited computational power in test time. In this framework, at training time, a reduced ground set is learned which will be used as a ground set at test time. This procedure will reduce the computational time in test time. More formally, the two-stage submodular optimization framework aims to solve the following problem. Let $f_i:2^{\mathcal{X}}\xrightarrow{}{\mathbb{R}}_+$ for $i\in [m]$, be a monotone submodular function over ground set $V$. The goal is to find $S$ with size at most $q$ whose subests of size $k$ maximize the sum of $f_i$ for $i\in [m]$: $$\label{eq:two-stage submodular}   \max_{S\subseteq {\mathcal{X}}, \mid S \mid\leq q}\; \frac{1}{m}\sum_{i=1}^{m}\; \max_{S_i\subseteq S, \mid S_i\mid \leq k}\; f_i(S_i)$$ Once the set $S$ is found, it will be used in the test phase (e.g., by running full greedy on $S$ as the reduced ground set) to find $k$ elements for a new task. This framework uses ${\mathcal{O}}(qk)$ function evaluations for each new test task; however, it poorly personalizes to a test task because the set $S$ has been optimized only for the tasks at the training time. This intuition is indeed consistent with our experimental findings reported below. We further remark that the two-stage framework requires very high computational power in training. For example, the Replacement-Greedy algorithm [@stan2017probabilistic] requires computational complexity ${\mathcal{O}}(qkmn)$ (which is a factor $q$ larger than the complexity of the algorithms in this paper). As a result of this issue, we were not able to run the state-of-the-art two-stage algorithms to solve in the setting considered in our main simulation results (presented in Section \[sec:Simulation\]). e.g., for ground set of size $n = 10^5$ our two-stage implementation would take a very long time.

We have considered the ride-sharing application discussed in Section \[sec:Simulation\] and let $n=500$ (ground set size), $m=50$ (number of tasks), and $k$ changing from 5 to 30 (cardinality constraint) while $l=80\%k$ (portion that will fill in the submodular meta-learning during training), and $q=100$ (size of reduced ground set for two-stage framework). For solving the two-stage problem we have used the Replacement-Greedy algorithm introduced in [@stan2017probabilistic]. We choose these parameters based on the following two facts:

1.  Because of the high computational cost of the Replacement Greedy algorithm in training for the ride-sharing application, we chose $n$ to be 500.

2.  We provide a fair comparison in terms of computational power at test time, which means both Meta-Greedy (our algorithm) and Replacement-Greedy have exactly *the same computational cost* at test time. Formally, $n(k-l)=qk$.

we report the result for the above setting in the Figure \[fig:twostage\]. A few comments are in order: (i) The two stage implementation reduces the ground set of size $n = 500$ to $q = 100$. When $k$ is small, some of the popular elements found at training time would be good enough to warrant a good performance at test time. However, when $k$ increases, the role of personalizing becomes more apparent. As we see, the performance of Replacement-Greedy does not improve much when we increase $k$ and it is close to the performance of Greedy-Train (which chooses all the $k$ elements during the training phase–see and the discussion therein). However, since Meta-Greedy does (a small) task-specific optimization at test time, its performance becomes much better. We emphasize again that, in order to be fair, the comparison in Figure \[fig:twostage\] has been obtained using *the same* computational power allowed at test time for both meta-learning and two-stage approaches.

Conclusion and Future Work
==========================

In this paper, we extended the notion of Model-Agnostic Meta-Learning (MAML) to discrete optimization and in particular to submodular maximization. We proposed a novel formulation in which we aim to find an initial solution set that can be quickly adapted to a new task at a relatively low computational cost. In our meta-learning framework, the process of selecting set items is done in two parts: In the first part, a set of items are selected offline according to prior experience and data. In the second part, which happens at test time, a set of elements that is personalized to the new revealed task is selected. For the proposed problem, we introduced a deterministic variant of the greedy algorithm which obtains a solution that is at least $0.53$-optimal, when the tasks are monotone and submodular. We further presented a randomized algorithm that improves this result and obtains $(1-1/e-o(1))$-approximation in expectation. We also studied the performance of our proposed meta-learning framework and algorithms for two real-world applications: movie recommendation and ride-sharing problems. Our numerical results indicate the advantage of our proposed scheme with respect to traditional learning procedures as well as methods based on two-stage submodular optimization.

There are numerous open directions that can be investigated along the lines of discrete meta-learning and user-specific adaptation for discrete problems (indeed, this work can be considered as a first step). Examples include extending the results to a more general setting when the tasks are (approximately) submodular but non-monotone, considering the case that the tasks at training and test times are drawn according to two different probability distributions (possibly with bounded distance), and desinig

Further, exploring meta-learning continuous extensions and

Acknowledgements {#acknowledgements .unnumbered}
================

The research of Arman Adibi and Hamed Hassani is supported by NSF award CPS-1837253, NSF CAREER award CIF 1943064, and Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award FA9550-20-1-0111.

Appendix {#appendix .unnumbered}
========

Proof of Proposition \[alg1lemma\] {#sec:proof_prop_1}
==================================

First, we prove lemma which will help us to show .

\[lemma:greedy procedure\] Consider the monotone submodular function $f$ where and the greedy procedure for maximizing it starting from $S^{'}$ and in $t^{th}$ step adding the element with maximum marginal gain $e^{(t)}$ to $S^{(t-1)}$ which means $e^{(t)}=\operatorname*{arg\,max}\limits_e f(S^{(t-1)}\cup e \cup S^{'})-f(S^{(t-1)}\cup S^{'})$, then the following holds for every set $T$ and $S^{''}$ where $S^{'}\subseteq T$ and $\mid T\mid=k$. $$\label{eq: eq1 pf lemma:greedy}
    f(S{''}\cup T ) -f( S^{(k)}\cup S{''})\leq f( S^{(k)}\cup S^{'})- f(S^{'})$$

To show define $J^{(t)}$ iteratively as follows. Start from $J^{(0)}=T$ and let $D^{(t)}=J^{(t-1)}\setminus S^{(t-1)}$ and define $o^{(t)}$ in the following way:

1.  If $e^{(t)}\in D^{(t)}$, then let $o^{(t)}=e^{(t)}$.

2.  Otherwise, if $e^{(t)}\notin D^{(t)}$, let $o^{(t)}$ be one of the elements of $D^{t}$ chosen uniformly at random.

Define $J^{(t)}:=J^{(t-1)}\cup e^{(t)}\setminus o^{(t)}$.\

(TS\^[”]{}) (TJ\^[(1)]{}) … (TJ\^[(t)]{})\
(S\^[(0)]{}S\^[’]{}) (S\^[(1)]{} S\^[’]{}) … (S\^[(t)]{}S\^[’]{})

\
then we can write the following inequalities: $$\begin{aligned}
f(S^{(t)}\cup S^{'})-f(S^{(t-1)}\cup S^{'})
&= f(S^{(t-1)}\cup e^{(t)}\cup S^{'})-f(S^{(t-1)}\cup S^{'})
\\\label{eq: chain1 l1:greedy}&\geq f(S^{(t-1)}\cup S^{'}\cup o_i^{(t)})-f(S^{(t-1)}\cup S^{'})
\\\label{eq: chain2 l1:greedy}&\geq f(J^{(t-1)}\cup S^{'})-f(J^{(t-1)}\cup S^{'}\setminus o^{(t)})\\&\geq f(J^{(t-1)}\cup S^{''})-f(J^{(t-1)}\cup S^{''}\setminus o^{(t)})
\\&\geq f(J^{(t-1)}\cup S^{''})-f(J^{(t-1)}\cup S^{''}\setminus o^{(t)}) \nonumber\\
&\quad-f(S^{''}\cup J^{(t-1)}\cup e^{(t)}\setminus o^{(t)})+f(S^{''}\cup J^{(t-1)}\setminus o^{(t)})\label{eq: chain3 l1:greedy}\\&= f(J^{(t-1)}\cup S^{''})-f(J^{(t-1)}\cup S^{''}\setminus o^{(t)}) \nonumber\\
&\quad-f(S^{''}\cup J^{(t)})+f(S^{''}\cup J^{(t-1)}\setminus o^{(t)})
\\&=f(J^{(t-1)}\cup S^{''})-f(S^{''}\cup J^{(t)})\end{aligned}$$ where follows from $f(S^{(t-1)}\cup e^{(t)} \cup S^{'})-f(S^{(t-1)}\cup S^{'})=\max\limits_e f(S^{(t-1)}\cup e \cup S^{'})-f(S^{(t-1)}\cup S^{'})\geq f(S^{(t-1)}\cup o^{(t)} \cup S^{'})-f(S^{(t-1)}\cup S^{'})$ and follows from submodularity since in each step $S^{(t-1)}\subseteq J^{(t-1)}$ and $o^{(t)}\not\in S^{(t-1)}$. Finally, equation follows from the fact that $-f(J^{(t-1)}\cup e^{(t)}\cup S^{''}\setminus o^{(t)})+f(J^{(t-1)}\cup S^{''}\setminus o^{(t)})\leq 0$. Then, by summing over the above inequality we get the following inequality: $$\begin{aligned}
f(S^{(t)}\cup S^{'})-f(S^{(0)}\cup S^{'})&=\sum_{i=0}^{t}f(S^{(i)}\cup S^{'})-f(S^{(i-1)}\cup S^{'})
\\&\geq \sum_{i=0}^{t} f(S^{''}\cup J^{(i-1)})-f(S^{''}\cup J^{(i)})
\\&=f(S^{''}\cup J^{(0)})-f(S^{''}\cup J^{(t)})
\\&\geq f(S^{''}\cup T)-f(S^{''}\cup J^{(t)})\end{aligned}$$ Note because of the definition of $J^{(t)}$ after k step $J^{(k)}=S^{(k)}$; therefore, we can conclude that: $$\begin{aligned}
f(S^{(k)}\cup S^{'})-f( S^{'})&\geq f(S^{''}\cup T)-f(S^{''}\cup J^{(t)})\notag\\&=f(S^{''}\cup T)-f(S^{''}\cup S^{(k)})\end{aligned}$$ .

Let ${S_{\rm{tr}}}$, $\{S_i\}_{i=1}^{m}$ be the output of Algorithm \[alg: discrete meta-Greedy\] and ${S_{\rm{tr}}}^{*}$, $\{S_i^{*}\}_{i=1}^{m}$ be the optimal solution for problem . We first show that the output of Algorithm \[alg: discrete meta-Greedy\] in phase 1 satisfies the following inequality: $$\label{eq: eq1 pf l1}
    \sum_{i=1}^m f_i({S_{\rm{tr}}}^{*} \cup S_i^{*}) - \sum_{i=1}^m f_i( {S_{\rm{tr}}})\leq  \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i^{*})$$

To show let $e^{(t)}$ be the ${t}^{th}$ element of greedy procedure in phase 1, and ${S_{\rm{tr}}}^{(t)}$ be the $t^{th}$ set in this procedure, where $e^{(t)}=\operatorname*{arg\,max}\limits_e \sum\limits_{i=1}^{m} f_i({S_{\rm{tr}}}^{(t-1)}\cup e)-f_i({S_{\rm{tr}}}^{(t-1)})$. let $J^{(0)}={S_{\rm{tr}}}^{*}$ and define $J^{(t)}$ iteratively as follows. Let $D^{(t)}=J^{(t-1)}\setminus {S_{\rm{tr}}}^{(t-1)}$ and define $o^{(t)}$ in the following way:

1.  If $e^{(t)}\in D^{(t)}$, then let $o^{(t)}=e^{(t)}$.

2.  Otherwise, if $e^{(t)}\notin D^{(t)}$, let $o^{(t)}$ be one of the elements of $D^{t}$ chosen uniformly at random.

Define $J^{(t)}:=J^{(t-1)}\cup e^{(t)}\setminus o^{(t)}$. We show this procedure in the following chain.\

([S\_[[tr]{}]{}]{}\^[\*]{},{S\_i\^[\*]{}}\_[i=1]{}\^[m]{}) (J\^[(1)]{},{S\_i\^[\*]{}}\_[i=1]{}\^[m]{}) … (J\^[(l)]{},{S\_i\^[\*]{}}\_[i=1]{}\^[m]{})\
([S\_[[tr]{}]{}]{}=,{S\_i\^0}\_[i=1]{}\^[m]{}=) ([S\_[[tr]{}]{}]{}\^[(1)]{},{}\_[i=1]{}\^[m]{}) … ([S\_[[tr]{}]{}]{}\^[(l)]{},{}\_[i=1]{}\^[m]{})

\
then we can write the following inequalities: $$\begin{aligned}
\sum_{i=1}^m f_i({S_{\rm{tr}}}^{(t)})-f_i({S_{\rm{tr}}}^{(t-1)})
&= \sum_{i=1}^m f_i({S_{\rm{tr}}}^{(t-1)}\cup e^{(t)})-f_i({S_{\rm{tr}}}^{(t-1)})
\\\label{eq: chain1 l1}&\geq \sum_{i=1}^m f_i({S_{\rm{tr}}}^{(t-1)}\cup o_i^{(t)})-f_i({S_{\rm{tr}}}^{(t-1)})
\\\label{eq: chain2 l1}&\geq \sum_{i=1}^m f_i(S_{i}^{*}\cup J^{(t-1)})-f_i(S_{i}^{*}\cup J^{(t-1)}\setminus o^{(t)})
\\&\geq \sum_{i=1}^m f_i(S_i^{*}\cup J^{(t-1)})-f_i(S_i^{*}\cup J^{(t-1)}\setminus o_i^{(t)}) \nonumber\\
&\quad+\sum_{i=1}^m -f_i(S_{i}^{*}\cup J^{(t)})+f_i(S_{i}^{*}\cup J^{(t-1)}\setminus o_i^{(t)})\label{eq: chain3 l1}
\\&=\sum_{i=1}^m f_i(S_{i}^{*}\cup J^{(t-1)})-f_i(S_{i}^{*}\cup J^{(t)})\end{aligned}$$ where follows from definition of $e^{(t)}$ and the greedy procedure and follows from submodularity since in each step ${S_{\rm{tr}}}^{(t-1)}\subseteq J^{(t-1)}$ and $o^{(t)}\not\in {S_{\rm{tr}}}^{(t-1)}$ and finally, equation follows from the fact that $-f_i(J^{(t)}\cup S_i^{*})+f_i(J^{(t-1)}\cup S_i^{*}\setminus o^{(t)})\leq 0$. Then, by summing over $t$ from 0 to $l$ we get the following inequality: $$\begin{aligned}
\sum_{i=1}^m f_i({S_{\rm{tr}}})=\sum_{i=1}^m f_i({S_{\rm{tr}}}^{(l)})-f_i({S_{\rm{tr}}}^{(0)})&=\sum_{i=1}^m\sum_{t=0}^{l}f_i({S_{\rm{tr}}}^{(t)})-f_i({S_{\rm{tr}}}^{(t-1)})
\\&\geq \sum_{i=1}^m\sum_{t=0}^{l}f_i(S_{i}^{*}\cup J^{(t-1)})-f_i(S_{i}^{*}\cup J^{(t)})
\\&=\sum_{i=1}^m f_i(S_{i}^{*}\cup J^{(0)})-f_i(S_{i}^{*}\cup J^{(l)})
\\&=\sum_{i=1}^m f_i(S_{i}^{*}\cup {S_{\rm{tr}}}^{*})-f_i(S_{i}^{*}\cup {S_{\rm{tr}}})\end{aligned}$$ where the last equality comes from the process of defining $J$. Because, we only change one element by adding element found in greedy process and removing one element from the optimal set in each step and the size of $J^{(t)}$ is $l$ in each step; therefore, after $l$ step $J^{(l)}={S_{\rm{tr}}}$. By rearranging the terms and summing over $i$ the claim in follows.\
\
Second, for the phase 2 of the algorithm \[alg: discrete meta-Greedy\] we can use the usual analysis of greedy[@krause2014submodular] for set $S_i$: $$\begin{aligned}
 \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)-f_i( {S_{\rm{tr}}})&\geq (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i^{opt})-f_i({S_{\rm{tr}}}))
\label{eq: eq3 pf l1 1} \\&\geq  (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i^{*})-f_i({S_{\rm{tr}}}))
 \label{eq: eq3 pf l1 2}\\&\geq  (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-2f_i({S_{\rm{tr}}}))
\label{eq: eq3 pf l1 3}\end{aligned}$$ where $S_i^{opt}=\operatorname*{arg\,max}\limits_{|S_i|\leq k-l}f_i({S_{\rm{tr}}}\cup S_i)$ in the equation . Equation follows from usual greedy analysis, equation follows from definition of ${S_{\rm{tr}}}^{opt}$, and equation  follows from equation .

Now divide both sides of by $1/m$ and regroup the terms to obtain $$\label{eq:result_alg_1_part_1}
    \frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i) \geq \left(1-\frac{1}{e}\right)({\rm{OPT}}-2\beta)+\beta,$$ where $\beta := \frac{1}{m}\sum_{i=1}^m f_i({S_{\rm{tr}}}).$

Finally, since $S_i\subseteq S_i\cup {S_{\rm{tr}}}$ by monotonicity [[$f_i(S_i\cup {S_{\rm{tr}}})\geq f_i({S_{\rm{tr}}})$]{}]{}. Then, combing this observation with the result in implies $$\frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}\cup S_i) \geq \max \biggl\{ \beta \,, \, (1-1/e)({\rm{OPT}} - 2\beta) + \beta \biggr \}.$$

Proof of Proposition \[alg2lemma\] {#sec:proof_prop_2}
==================================

Let ${S_{\rm{tr}}}$, $\{S_i\}_{i=1}^{m}$ be the output of Algorithm \[alg: Reverse discrete meta-Greedy\] and ${S_{\rm{tr}}}^{*}$, $\{S_i^{*}\}_{i=1}^{m}$ be the optimal solution for problem . We first show the following about the output of algorithm \[alg: Reverse discrete meta-Greedy\], phase 1.

$$\label{eq: eq1 pf l2}
    \sum_{i=1}^m f_i({S_{\rm{tr}}}^{*} \cup S_i^{*}) - \sum_{i=1}^m f_i( S_i)\leq  \sum_{i=1}^m f_i({S_{\rm{tr}}}^{*} \cup S_i)$$

to show consider the following: let $e_i^{(t)}=\operatorname*{arg\,max}\limits_e f_i(S_i^{(t-1)}\cup e)-f_i(S_i^{(t-1)})$. let $J^{(0)}_i=S_i^{*}$ and define $J^{(t)}_i$ iteratively as follows. Let $D^{t}_{i}=J^{(t-1)}_i\setminus S^{(t-1)}_i$ and define $o_i^{(t)}$ in the following way:

1.  If $e_i^{(t)}\in D^{t}_{i}$, then $o^{(t)}=e_i^{(t)}$;

2.  Otherwise, if $e_i^{(t)}\notin D^{t}_{i}$, let $o_i^{(t)}$ be one of the elements of $D^{t}_{i}$ chosen uniformly at random;

Define $J^{(t)}_i:=J^{(t-1)}_i\cup e_i^{(t)}\setminus o_i^{(t)}$.\

([S\_[[tr]{}]{}]{}\^[\*]{},{S\_i\^[\*]{}}\_[i=1]{}\^[m]{}) ([S\_[[tr]{}]{}]{}\^[\*]{},{J\_i\^[(1)]{}}\_[i=1]{}\^[m]{}) … ([S\_[[tr]{}]{}]{}\^[\*]{},{J\_i\^[(k-l)]{}}\_[i=1]{}\^[m]{})\
([S\_[[tr]{}]{}]{}=,{S\_i\^0}\_[i=1]{}\^[m]{}=) (,{S\_i\^[(1)]{}}\_[i=1]{}\^[m]{}) … (,{S\_i\^[(k-l)]{}}\_[i=1]{}\^[m]{})

\
then we can write the following inequalities: $$\begin{aligned}
f_i(S_i^{(t)})-f_i(S_i^{(t-1)})
&= f_i(S_i^{(t-1)}\cup e_i^{(t)})-f_i(S_i^{(t-1)})
\\\label{eq: chain1}&\geq f_i(S_i^{(t-1)}\cup o_i^{(t)})-f_i(S_i^{(t-1)})
\\\label{eq: chain2}&\geq f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)})-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)}\setminus o_i^{(t)})
\\&\geq f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)})-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)}\setminus o_i^{(t)}) \nonumber\\
&\quad-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t)})+f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)}\setminus o_i^{(t)})\label{eq: chain3}
\\&=f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)})-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t)})\end{aligned}$$ where follows from definition of $e_i^{(t)}$ and the greedy procedure and follows from the submodularity since in each step $S_i^{(t-1)}\subseteq J_i^{(t-1)}$ and $o_i^{(t)}\not\in S_i^{(t-1)}$ and finally, equation follows from the fact that $-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t)})+f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)}\setminus o_i^{(t)})\leq 0$ because of monotonicity. Then, by summing over $t$ from 0 to $k-l$ we get the following inequality: $$\begin{aligned}
f_i(S_i)=f_i(S_i^{(k-l)})-f_i(S_i^{(0)})&=\sum_{t=0}^{k-l}f_i(S_i^{(t)})-f_i(S_i^{(t-1)})
\\&\geq \sum_{t=0}^{k-l}f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t-1)})-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(t)})
\\&=f_i({S_{\rm{tr}}}^{*}\cup J_i^{(0)})-f_i({S_{\rm{tr}}}^{*}\cup J_i^{(k-l)})
\\&=f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-f_i({S_{\rm{tr}}}^{*}\cup S_i)\end{aligned}$$ where the last equality comes from the process of defining $J_i^{(k-l)}$; since, the size of $J_i^{(t)}$ is $k-l$ in each step and after $k-l$ step $J_i^{(k-l)}=S_i$. Then, by rearranging and summing over $i$ we can obtain .\
\
Second, for phase 2 of algorithm \[alg: Reverse discrete meta-Greedy\] we can use the usual analysis of greedy[@krause2014submodular] for set ${S_{\rm{tr}}}$ : $$\begin{aligned}
 \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)-f_i( S_i)&\geq (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}^{opt}\cup S_i)-f_i(S_i))
\label{eq: eq3 pf l2 1} \\&\geq  (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}^{*}\cup S_i)-f_i(S_i))
 \label{eq: eq3 pf l2 2}\\&\geq  (1-\frac{1}{e})(\sum_{i=1}^m f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-2f_i(S_i))
\label{eq: eq3 pf l2 3}\end{aligned}$$ where ${S_{\rm{tr}}}^{opt}=\operatorname*{arg\,max}\limits_{|{S_{\rm{tr}}}|\leq l}\sum\limits_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)$ in equation . Equation follows from the usual greedy analysis, equation follows from the definition of ${S_{\rm{tr}}}^{opt}$, and equation follows the from equation .

Now divide both sides of by $1/m$ and regroup the terms to obtain $$\label{eq:result_alg_2_part_1}
    \frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i) \geq \left(1-\frac{1}{e}\right)({\rm{OPT}}-2\gamma)+\gamma,$$ where $\gamma := \frac{1}{m}\sum_{i=1}^m f_i(S_i).$

Finally, since $S_i\subseteq S_i\cup {S_{\rm{tr}}}$ by monotonicity $f_i(S_i\cup {S_{\rm{tr}}})\geq f_i(S_i)$. Then, by combing this result wit we obtain $$\frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}\cup S_i) \geq \max \biggl\{ \gamma \,, \, (1-1/e)({\rm{OPT}} - 2\gamma) + \gamma \biggr \}.$$

The following shows the ratio of lower bound to optimum (a similar plot can be obtained for the lower bound of Proposition \[alg1lemma\] when $\gamma$ is replaced with $\beta$.). As we observe, in the worst case, the approximation factor is $0.5$.

![y-axis: The lower bound of Proposition \[alg2lemma\] divided by OPT, x-axis: $\gamma/\text{OPT}$.[]{data-label="fig:bound"}](boundplot.eps){width="8cm"}

Proof of Theorem \[thm:meta-greedy\] {#sec:proof_of_main_thm}
====================================

Let $\theta_2=\frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)})$. Since ${S_{\rm{tr}}}^{(2)}$ found greedily given $\{S_i\}_{i=1}^{m}$ we can write:

$$\label{eq: thm1 pf eq1}
\theta_2-\gamma\geq ({\rm{OPT}}-\gamma)(1-\frac{1}{e})\geq( \frac{1}{m} \sum_{i=1}^{m}   f_i(S^{'} \cup S_i^{(2)})-\gamma)(1-\frac{1}{e})$$

for every $\mid S^{'}\mid\leq l$. Also, we can write $$\begin{aligned}
   {\rm{OPT}}-\gamma&= \frac{1}{m}\sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-f_i(S_i^{(2)})
   \label{eq:tm1 pf align 1} \\&\leq \frac{1}{m}\sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{(2)} \cup S_i^{*})-f_i(S_i^{(2)})
   \label{eq:tm1 pf align 2} \\&= \frac{1}{m}\sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{(2)} \cup S_i^{*})+f_i({S_{\rm{tr}}}^{*} \cup S_i^{(2)})-f_i({S_{\rm{tr}}}^{*} \cup S_i^{(2)})-f_i(S_i^{(2)})
   \label{eq:tm1 pf align 3} \\&\leq \frac{1}{m}\sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{(2)} \cup S_i^{*})-f_i({S_{\rm{tr}}}^{*} \cup S_i^{(2)})+\frac{\theta_2-\gamma}{1-1/e}
   \label{eq:tm1 pf align 4}\\&\leq \frac{1}{m}\sum_{i=1}^{m}f_i( S_i^{(2)} \cup S_i^{*})-f_i( S_i^{(2)})+\frac{\theta_2-\gamma}{1-1/e}
   \label{eq:tm1 pf align 5}\end{aligned}$$ where comes from , and comes from submodularity. We thus obtain $$\label{eq: thm l1 1}
 {\rm{OPT}} -\frac{\theta_2-\gamma}{1-1/e}-\gamma \leq \frac{1}{m}\sum_{i=1}^{m}f_i( S_i^{(2)} \cup S_i^{*})-f_i( S_i^{(2)})$$ Also we can write for any set $S'$ such that $\mid S^{'}\mid\leq l$: $$\begin{aligned}
   \label{eq:tm1 pf align2 1}
    \frac{1}{m}\sum_{i=1}^{m}f_i(S^{'}\cup S_i^{*})-f_i(S^{'})
     &\geq \frac{1}{m}\sum_{i=1}^{m}f_i(S^{'}\cup S_i^{*}\cup S_i)-f_i(S^{'}\cup S_i)\\
     \label{eq:tm1 pf align2 2}
     &\geq \frac{1}{m}\sum_{i=1}^{m}f_i(S^{'}\cup S_i^{*}\cup S_i)-f_i(S_i)+f_i(S_i)-f_i(S^{'}\cup S_i)\\  \label{eq:tm1 pf align2 3}
     &\geq \frac{1}{m} \sum_{i=1}^{m}f_i( S_i^{*}\cup S_i)-f_i(S_i)+f_i(S_i)-f_i(S^{'}\cup S_i)\\
     \label{eq:tm1 pf align2 4}
     &\geq  {\rm{OPT}} -\frac{\theta_2-\gamma}{1-1/e}-\gamma+ \frac{1}{m} \sum_{i=1}^{m}f_i(S_i)-f_i(S^{'}\cup S_i)\\
      \label{eq:tm1 pf align2 5}
     &\geq  {\rm{OPT}} -2\frac{\theta_2-\gamma}{1-1/e}-\gamma\end{aligned}$$ where follows from submodularity, follows from monotonicity, and follows from , and follows from . This results the following for any set $S'$ such that $|S^{'}|\leq l$: $$\label{eq: thm l1 2}
     \frac{1}{m} \sum_{i=1}^{m}f_i(S^{'}\cup S_i^{*})-f_i(S^{'})  \geq  {\rm{OPT}} -2\frac{\theta_2-\gamma}{1-1/e}-\gamma$$ Now, from we can find a new bound for the performance of algorithm \[alg: main discrete meta-Greedy\]. From we can write:

$$\label{eq: thm1 pf eq2}
    \frac{1}{m}  \sum_{i=1}^{m}f_i({S_{\rm{tr}}}^{(1)}\cup S_i^{*})-f_i({S_{\rm{tr}}}^{(1)})  \geq  {\rm{OPT}} -2\frac{\theta_2-\gamma}{1-1/e}-\gamma$$

Also, since in Algorithm 1 the set $S_i^{(1)}$ is constructed greedily on the top of ${S_{\rm{tr}}}^{(1)}$, we have: $$\begin{aligned}
\label{eq: thm1 pf eq3}
\frac{1}{m} \sum_{i=1}^{m}   f_i({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)})-\beta
&\geq( \frac{1}{m} \sum_{i=1}^{m}   f_i({S_{\rm{tr}}}^{(1)} \cup S_i^{*})-\beta)(1-\frac{1}{e})\\
&\geq ( {\rm{OPT}} -2\frac{\theta_2-\gamma}{1-1/e}-\gamma)(1-\frac{1}{e}),\label{eq: thm1 pf eq3}\end{aligned}$$ where follows from . We thus obtain:

$$\begin{aligned}
\label{eq: thm1 pf eq4}
\frac{1}{m} \sum_{i=1}^{m}   f_i({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)})
\geq (  {\rm{OPT}} -2\frac{\theta_2-\gamma}{1-1/e}-\gamma)(1-\frac{1}{e})+\beta\end{aligned}$$

Using the same procedure as above, by defining $\theta_1= \frac{1}{m} \sum_{i=1}^{m}   f_i({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)})$, we can prove: $$\begin{aligned}
\label{eq: thm1 pf eq5}
\frac{1}{m} \sum_{i=1}^{m}   f_i({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)})
\geq (  {\rm{OPT}} -2\frac{\theta_1-\gamma}{1-1/e}-\gamma)(1-\frac{1}{e})+\beta\end{aligned}$$ which results in the following lower bound: $$\begin{aligned}
&\max \biggl\{ \frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)}) \, , \, \frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)}) \biggr\} \nonumber\\
&   \geq \max \biggl\{\theta_1, \theta_2,  (1-1/e)({\rm{OPT}} \!-\!\gamma) + \beta -2 (\theta_2-\gamma) ,(1-1/e)({\rm{OPT}} \!-\!\beta) + \gamma -2 (\theta_1-\beta) \biggr\}.\label{eq:thm p6}\end{aligned}$$

Finally, given and , the factor $0.53$ is obtained as a result of the following procedure. Let $\beta$ and $\gamma$ given as $\beta :=  \frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}^{(1)})$ and $\gamma := \frac{1}{m} \sum_{i=1}^m f_i(S_i^{(2)})$. Then the left-hand-side term in is lower bounded by:

\[eq: thm1 opt\] $$\begin{aligned}
{4}
\min\limits_{\theta_1, \theta_2} & \,\,  \max \biggl\{\theta_1, \theta_2,  (1-1/e)({\rm{OPT}} \!-\!\gamma) + \beta -2 (\theta_2-\gamma) ,  (1-1/e)({\rm{OPT}} \!-\!\beta) + \gamma -2 (\theta_1-\beta) \biggr\}
\\
&  \operatorname*{subject\,\, to \quad}\theta_1 \geq \max\{\beta,  (1-1/e)({\rm{OPT}} - 2\beta) + \beta\}  \\
& \!\qquad \quad \quad \quad \quad \theta_2 \geq \max\{\gamma,  (1-1/e)({\rm{OPT}} - 2\gamma) +\gamma\}  \end{aligned}$$

Note that the constraints hold due to the results of Proposition 1 and 2. In particular, the above bound is always larger than $ 0.53 \times \rm{OPT} $ for any value of $\beta$ and $\gamma$.

Proof of Theorem \[thm: randomized meta\] {#sec:proof_of_main_random_theorem}
=========================================

Consider round $t$ in which $\mid {S_{\rm{tr}}}\mid<l$ and $\mid S_i \mid<k-l$ the expected gain of the algorithm with probability $\frac{l}{k}$ is the maximum gain from adding an element $e^{*}=\operatorname*{arg\,max}\limits_e \sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{t}\cup{e}\cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t)$ or with probability $\frac{k-l}{k}$ the gain is $\sum\limits_{i=1}^{m}\max_{e_i}f_i({S_{\rm{tr}}}^{t}\cup{e_i} \cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t)$ which can be written as follows.

$$\begin{aligned}
    \mathbb{E}[&\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{t+1}\cup S_i^{t+1})-f_i({S_{\rm{tr}}}^t\cup S_i^t)|{S_{\rm{tr}}}^{t},S_i^t]\nonumber\\=&\frac{l}{k}\max_e\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{t}\cup{e}\cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t)+\frac{k-l}{k}\sum\limits_{i=1}^{m}\max_{e_i}f_i({S_{\rm{tr}}}^{t}\cup{e_i} \cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t)\label{eq: rand alg pf eq begin}\end{aligned}$$

assuming ${S_{\rm{tr}}}^* , S_i^{*}$ is optimal solution, we can also write: $$\begin{aligned}
   \frac{1}{k}\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-f_i({S_{\rm{tr}}}^t\cup S_i^t)
   &\leq \frac{1}{k}\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{*}\cup {S_{\rm{tr}}}^t\cup S_i^t)-f_i({S_{\rm{tr}}}^t\cup S_i^t)
   \label{eq: rand alg pf eq 1} \\&\leq \frac{1}{k}\sum_{e\in {S_{\rm{tr}}}^{*}\setminus {S_{\rm{tr}}}^t}\sum\limits_{i=1}^{m}f_i({e} \cup {S_{\rm{tr}}}^t\cup S_i^t)-f_i( {S_{\rm{tr}}}^t\cup S_i^t)
\nonumber\\&+\frac{1}{k}\sum\limits_{i=1}^{m}\sum_{e\in S_i^{*}\setminus S_i^t}f_i({e} \cup {S_{\rm{tr}}}^t\cup S_i^t)-f_i( {S_{\rm{tr}}}^t\cup S_i^t)
  \label{eq: rand alg pf eq 2}   \\&\leq \frac{l}{k}\max_e\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{t}\cup{e}\cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t)
    \nonumber\\&+\frac{k-l}{k}\sum\limits_{i=1}^{m}\max_{e_i}f_i({S_{\rm{tr}}}^{t}\cup{e_i} \cup S_i^{t})-f_i({S_{\rm{tr}}}^t\cup S_i^t) \label{eq: rand alg pf eq 3}\end{aligned}$$ where follows from monotonicity, and follows from submodularity. Then, from and we conclude that: $$\begin{aligned}
    \mathbb{E}[&\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{t+1}\cup S_i^{t+1})-f_i({S_{\rm{tr}}}^t\cup S_i^t)|{S_{\rm{tr}}}^{t},S_i^t]\leq\frac{1}{k}\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{*}\cup S_i^{*})-f_i({S_{\rm{tr}}}^t\cup S_i^t)
  \label{eq: rand alg pf eq final}\end{aligned}$$ In other words, the expected improvement in the objective (left-hand side of ) is at least $1/k$ times the gap of the current objective value to OPT (i.e. right-hand side of ). Note that is only valid when $\mid {S_{\rm{tr}}}\mid<l$ and $\mid S_i \mid<k-l$. Hence, by defining the stopping time $\tau$ as first time that either $\mid {S_{\rm{tr}}}\mid=l$ or $\mid S_i \mid=k-l$, and a telescopic usages of the bounds in , we obtain the following bound: $$\begin{aligned}
\mathbb{E} \left[ \frac{1}{m}\sum\limits_{i=1}^{m}f_i({S_{\rm{tr}}}^{\tau}\cup S_i^{\tau}) \right]\nonumber\geq \text{OPT}  \times \mathbb{E} \left[\left(1-\left(1-\frac{1}{k}\right)^\tau\right)\right]\end{aligned}$$ The following theorem finds an upper bound on $\mathbb{E}[(1-\frac{1}{k})^\tau]$ which finishes the proof.

\[thm: tau analyze randomized meta convergence\] If stopping time $\tau$ is first time that either $\mid {S_{\rm{tr}}}\mid=l$ or $\mid S_i \mid=k-l$ then $\mathbb{E}[(1-\frac{1}{k})^\tau]\leq c+\exp(-1+\sqrt{3c.log(\frac{k}{c}}))$ where $c=\frac{1}{\min\{l,k-l\}}$.

let $u_1, u_2, \cdots$ be $i.i.d$ random variables with distribution $u_i \sim \text{Bernoulli}(1 - l/k)$, i.e. $p(u_i = 1) = (k-l)/k$. The stopping time $\tau$ is the first time that $\sum_{i=1}^{\tau}u_i=k-l$ or $\tau - \sum_{i=1}^{\tau}u_i = l$. Let us define $X_r=\sum_{i=1}^{r}u_i$. As a result, $\tau=r$ if and only if either $X_r=k-l$ or $X_r=r-l$. Assume without loss of generality $k-l \leq l$ which means $\max\{\sqrt{1/(k-l)},\sqrt{1/l}\}=\sqrt{1/(k-l)}$. Then, we can write: $$\begin{aligned}
 \nonumber
 \mathbb{E}[(1-\frac{1}{k})^\tau]&\leq \sum_{r=1}^{k-1}(1-\frac{1}{k})^{r}[p(X_r=k-l)+p(X_r=r-l)]\\&\leq\sum_{r=1}^{k-1}\text{exp}(\frac{-r}{k})[p(X_r=k-l)+p(X_r=r-l)] \label{eq_partition}\end{aligned}$$ We focus on the first term in and show that it is less than $e^{-1 + c}/2$. The second term can be shown similarly to have the same upper bound. By using Sterling and Chernoff bounds we can find upper bound on $p(X_r=k-l)$ as follows: $$\begin{aligned}
 p(X_r=k-l)&\leq \frac{1}{\sqrt{r}}\text{exp}(-\frac{(k-r)^2(k-l)}{3kr})\\&\leq
 \frac{1}{\sqrt{r}}\text{exp}(-\frac{(k-r)^2(k-l)}{3k^2})\end{aligned}$$

As a result: $$\begin{aligned}
 \sum_{r=1}^{k-1} \text{exp}(\frac{-r}{k})[p(X_r=k-l)]&\leq  \sum_{r=1}^{k-1} \frac{1}{\sqrt{r}}\text{exp}(\frac{-r}{k})\text{exp}(-\frac{(k-r)^2(k-l)}{3k^2})\\&\leq \sum_{i=0}^{ 2\sqrt{k-l} -1 }\frac{1}{\sqrt{k(1-\frac{i}{2\sqrt{k-l}})}}\text{exp}(\frac{-i^2}{12})\text{exp}(-1+\frac{i}{2\sqrt{k-l}})\\&\leq \text{exp}(-1+\frac{1}{\sqrt{k-l}})\sum_{i=0}^{2\sqrt{k-l}-1}\frac{1}{\sqrt{k(1-\frac{i}{2\sqrt{k-l}})}}\text{exp}(\frac{-i^2}{12})\text{exp}(\frac{i-1}{2\sqrt{k-l}})\end{aligned}$$ where one can show using Gaussian integrals that $\sum\limits_{i=0}^{2\sqrt{k-l}-1}\frac{1}{\sqrt{k(1-\frac{i}{2\sqrt{k-l}})}}\text{exp}(\frac{-i^2}{12})\text{exp}(\frac{i-1}{2\sqrt{k-l}})$ is always less than 0.5[@bullen1998dictionary]. Therefore, $\sum\limits_{r=1}^{k-1} \text{exp}(\frac{-r}{k})[p(X_r=k-l)]\leq \frac 12 \text{exp}(-1+\frac{1}{\sqrt{k-l}})$ Similarly, we can use the same argument to prove $\sum\limits_{r=1}^{k-1} \text{exp}(\frac{-r}{k})[p(X_r=r-l)]\leq \frac12 \text{exp}(-1+\frac{1}{\sqrt{k-l}})$, which finishes the proof.

Furthermore, we define $\tau^{'}=r$ when $r$ is the first time that $X_r=r-l$ and $\tau^{''}=r$ when $r$ is the first time that $X_r=k-l$. Also, let $c=\frac{1}{\min\{l,k-l\}}$ as it was defined in the lemma. By this definition, $\tau=\min\{\tau^{''},\tau^{'}\}$ and we can write the following about the probabilities of $\tau^{'}$ and $\tau^{''}$: $$p(\tau^{'}=r)={r-1 \choose l-1}(\frac{k-l}{k})^
{r-l}(\frac{l}{k})^{l}$$ $$p(\tau^{''}=r)={r-1 \choose k-l-1}(\frac{l}{k})^
{r-k+l}(\frac{k-l}{k})^{k-l}$$

then, based on the definition of $\tau^{'}$ and $\tau^{''}$ we have the following properties for $\tau^{'}$ and $\tau^{''}$:

-   if $r<k-l$ then $p(\tau^{''}=r)=0$.

-   if $r<l$ then $p(\tau^{'}=r)=0$.

-   if $r>k$ then $p(\tau^{'}\leq \tau^{''}|\tau^{'}=r)=0$.

-   if $r<k$ then $p(\tau^{'}\leq \tau^{''}|\tau^{'}=r)=1$.

-   if $r<k$ then $p(\tau^{'}\geq \tau^{''}|\tau^{''}=r)=1$

-   if $r>k$ then $p(\tau^{'}\geq \tau^{''}|\tau^{''}=r)=0$.

-   $p(\tau^{''}=r|\tau^{'}\geq \tau^{''})=p(\tau=r|\tau^{'}\geq \tau^{''})$.

-   $p(\tau^{'}=r|\tau^{'}\leq \tau^{''})=p(\tau=r|\tau^{'}\leq \tau^{''})$.

Moreover using Bayes rule we can write:

-   $$p(\tau^{'}=r|\tau^{'}\leq \tau^{''})=\frac{p(\tau^{'}\leq \tau^{''}|\tau^{'}=r)p(\tau^{'}=r)}{p(\tau^{'}\leq \tau^{''})}=\frac{\mathbbm{1}(r\leq k)p(\tau^{'}=r)}{p(\tau^{'}\leq \tau^{''})}.$$

-   $$p(\tau^{''}=r|\tau^{'}\geq \tau^{''})=\frac{\mathbbm{1}(r\leq k)p(\tau^{''}=r)}{p(\tau^{''}\leq \tau^{'})}.$$

Let $\bar{X_r}=r-X_r$ we can write $\bar{X_r}=\sum_{i=1}^{r}v_i$ where $v_1,v_2,v_3,\dots$ are $i.i.d$ random variable with distribution $v_i\sim \text{Bernoulli}(l/k)$. Then, we can write the following using Chernoff bound: $$\begin{aligned}
    p(\tau^{'}=r)
    &\leq p(X_r= r-l)
    \\&\leq p(\bar{X_r}\geq l)
    \\&\leq p(\bar{X_r}\geq r(\frac{l}{k})-(k-r)\frac{l}{k})
    \\&\leq \exp{\left(-\frac{(k-r)^2(\frac{l}{k})^2}{3r(\frac{l}{k})}\right)}
    \\&=\exp{\left(-\frac{(k-r)^2(l)}{3rk}\right)}\end{aligned}$$ Similarly: $$\begin{aligned}
    p(\tau^{''}=r)
    &\leq p(X_r= k-l)
    \\&\leq p({X_r}\geq k-l)
    \\&\leq p({X_r}\geq r(1-\frac{l}{k})-(k-r)(1-\frac{l}{k}))
    \\&\leq \exp{\left(-\frac{(k-r)^2(1-\frac{l}{k})^2}{3r(1-\frac{l}{k})}\right)}
    \\&\leq \exp{\left(-\frac{(k-r)^2(k-l)}{3rk}\right)}
        \\&\leq \exp{\left(-\frac{(k-r)^2}{3rkc}\right)}\end{aligned}$$ then we can write the $\mathbb{E}[(1-\frac{1}{k})^\tau]$ as follows:

$$\begin{aligned}
 \label{eq:pf expectation}
 \mathbb{E}[(1-\frac{1}{k})^\tau]&=\sum_{r=1}^{k}(1-\frac{1}{k})^rp(\tau=r)\leq(1-\frac{1}{k})^{k-\alpha \sqrt{c}}+\sum_{r=1}^{k-\alpha \sqrt{c}}(1-\frac{1}{k})^rp(\tau=r)\end{aligned}$$

Our goal is to find proper bound for . we focus on the second term in - and try to find proper bound for it.

$$\begin{aligned}
\sum_{r=1}^{k-\alpha \sqrt{c}}&(1-\frac{1}{k})^rp(\tau=r)
 \label{eq:pf thm2  2nd term eq1}\\&=\sum_{r=1}^{k-\alpha \sqrt{c}}(1-\frac{1}{k})^r(p(\tau^{'}=r|\tau^{'}< \tau^{''})p(\tau^{'}<\tau^{''})+ p(\tau^{''}=r|\tau^{'}\geq \tau^{''})p(\tau^{'}\geq\tau^{''}))
 \label{eq:pf thm2  2nd term eq2}\\&=\sum_{r=1}^{k-\alpha \sqrt{c}}(1-\frac{1}{k})^r(p(\tau^{'}=r)+ p(\tau^{''}=r))
 \label{eq:pf thm2  2nd term eq3}\\&=\sum_{r=l}^{k-\alpha \sqrt{c}}(1-\frac{1}{k})^rp(\tau^{'}=r)+\sum_{r=k-l}^{k-\alpha \sqrt{c}}(1-\frac{1}{k})^r p(\tau^{''}=r)
 \label{eq:pf thm2  2nd term eq4}\\& \leq \sum_{r=l}^{k-\alpha \sqrt{c}}\exp{\left(-\frac{(k-r)^2}{3rkc}\right)}   +  \sum_{r=k-l}^{k-\alpha \sqrt{c}} \exp{\left(-\frac{(k-r)^2}{3rkc}\right)}
  \label{eq:pf thm2  2nd term eq5}\\& \leq (k-l)\exp{\left(-\frac{(k-(k-\alpha \sqrt{c}))^2}{3k^2c}\right)}   +  l \exp{\left(-\frac{(k-(k-\alpha \sqrt{c}))^2l}{3k^2}\right)}
   \label{eq:pf thm2  2nd term eq6}\\& \leq (k-l)\exp{\left(-\frac{(\alpha \sqrt{c})^2}{3k^2c}\right)}   +  l \exp{\left(-\frac{(\alpha \sqrt{c})^2l}{3k^2}\right)}
   \label{eq:pf thm2  2nd term eq7}\end{aligned}$$

where follows from law of total probability, follows from bayes rule, follows from Chernoff bound, follows from the fact that $r<k$. Let $\alpha=3\sqrt{\log(\frac{1}{c})}.k$. As result, we have: $$\begin{aligned}
 \sum_{r=1}^{k-\alpha \sqrt{c}}&(1-\frac{1}{k})^rp(\tau=r)\leq  (k-l)c^{3}   +  l c^{3cl}  \end{aligned}$$ Assume without loss of generality $k-l\leq l$ and $k-l\geq 2$. As a result, $c=\frac{1}{k-l}$. we want to show that $(k-l)c^{3}   +  l c^{3cl}=c^2+lc^{3cl}\leq c$. To show this, we show the following equivalent inequality : $$\begin{aligned}
 l (k-l)^{-3cl}\leq c(1-c)=\frac{k-l-1}{(k-l)^2}\end{aligned}$$ This holds since $k-l\geq 2$ we have $ \frac{l}{(k-l)^3} (k-l)^{-3(cl-1)}\leq  \frac{l}{(k-l)^3} 2^{-3(\frac{l}{k-l}-1)}\leq \frac{l}{(k-l)^3\frac{l}{k-l}}=\frac{1}{(k-l)^2}\leq \frac{k-l-1}{(k-l)^2}$. Moreover, we can bound the first term in as follows: $$\begin{aligned}
 (1-\frac{1}{k})^{k-\alpha \sqrt{c}}\leq \exp(-1+3\sqrt{c.\log(\frac{1}{c}}))\end{aligned}$$ summing up we can find the following bound for $\mathbb{E}[(1-\frac{1}{k})^\tau]$ which finishes the proof.

$$\begin{aligned}
 \mathbb{E}[(1-\frac{1}{k})^\tau]&\leq c+\exp(-1+3\sqrt{c.log(\frac{1}{c}}))\end{aligned}$$

Continuous Algorithm for Submodular Meta-Learning
=================================================

In this section, we provide method that accomplish $1-1/e$ approximation ratio for problem \[eq:ML\_submodular\_sample\_avg\] . In high level, we use the continuous optimization method and dependent rounding technique in [@balkanski2016learning] to obtain a solution.\
\
**New Ground Set:** Similar to [@balkanski2016learning], we define new ground set of size $nm+n$ which has the orginal ground set elements and element for every $(element, function)$ pair ${\mathcal{X}}^{'}=V \cup \{a_{i,j}\}_{i\in[n],j\in[m]}$.

$$\label{eq:cont reformulation}
    g(S)=\sum_{j=1}^{m} f_j(\{a_i: a_{i,j}\in S\})$$

\
\
**Continuous problem:** let us associate with each element $a_{i}$ a variable $x_i \in [0,1]$ and for each element $a_{i,j}$ a variable $x_{i,j} \in [0,1]$; then, we define the $G(x)$ as in : $$\label{eq:cont obj1}
    G(x)= \mathbb{E}_{s \sim D(x)}g(S)$$ where $D(x)$ is the following distribution:

1.  $a_i \in S \sim D(x)$ for each i independently with probability $x_i$

2.  $a_{i,j} \in S \sim D(x)$ for each i and for each j independently with probability $\frac{x_{i,j}}{x_i}$ if $a_i \in S$ and with probability 0 otherwise.

we can write the continuous version of the problem as note that the difference between this problem and two-stage submodular problem shows itself in .

\[eq: cont\] $$\begin{aligned}
{4}
& \max_{\mathcal{S}}&& G(x)
\\
&\operatorname*{subject\,\, to \quad}&& x_i\in [0,1]&&&\forall i\in[n]\\
&  && x_{i,j}\in [0,1]&&&\forall i\in[n]\forall j\in[m]\\
&  && x_{i} \leq x_{i,j} \;\;\;&&&\forall j\in[m]\label{eq: dif two-stage meta sub}\\
&  && \sum_{j} x_{i,j} \leq k \;\;\;\\
&  && \sum_{i} x_{i} \leq l \;\;\;\end{aligned}$$

\[lemma: cont\] $G_{ME}=G$ for every x where $$\label{eq:cont obj}
    G_{ME}(x)= \mathbb{E}_{s \sim x}g(S)$$

[@balkanski2016learning] then we can reformulate the problem as:

\[eq: cont2\] $$\begin{aligned}
{4}
& \max_{\mathcal{S}}&& G_{ME}(x)
\\
&\operatorname*{subject\,\, to \quad}&& x_i\in [0,1]&&&\forall i\in[n]\\
&  && x_{i,j}\in [0,1]&&&\forall i\in[n]\forall j\in[m]\\
&  && x_{i} \leq x_{i,j} \;\;\;&&&\forall j\in[m]\\
&  && \sum_{j} x_{i,j} \leq k \;\;\;\\
&  && \sum_{i} x_{i} \leq l \;\;\;\end{aligned}$$

Lemma \[lemma: cont\] reduces the problem to submodular maximization over solvable polytope [@calinescu2011maximizing] which can be solve using continuous greedy method and the solution achieves $(1- \frac{1}{e})$ approximation ratio. But, this algorithm is very slow and can not be use in applications with large amount of data.

Generalization of Submodular Meta-Learning
------------------------------------------

Generalization of submodular maximization has been studied before as $k$-submodularity . The $k$-submodularity studies function of $k$ subset of ground set which are disjoint. And function is submodular in each set[@ohsaka2015monotone]. However, in submodular meta-learning framework, sets can overlap and we don’t have disjoint restriction on the sets. Therefore, we need to come up with more general notion that can be generalize submodular meta-learning. We introduce the notion of orthant-submodularity and propose two algorithm to solve this problem.

### General Submodular Meta-Learning Formulation

A inherent structure of submodular meta-learning involves the m subsets of ground set which lead us to generalize to more general case in which we are dealing with general function of m subsets of ground set. In order to pursue this goal we need to define following definitions.

**Set of m-tuples.** Let ${\mathcal{X}}$ be finite set of elements of size n, and ${\mathcal{Y}}:=2^{\mathcal{X}}$ be the all the subset of ${\mathcal{X}}$, we call ${\mathcal{Y}}^m:=\{(S_1,S_2,\dots,S_m)|\;S_i\in{\mathcal{Y}}\;\}$ set of all m-tuples.

**Partial Order on m-tuples.** For two element ${\mathcal{S}}\, , \,{\mathcal{S}}^{'}\in{\mathcal{Y}}^m$ we call ${\mathcal{S}}\leq {\mathcal{S}}^{'}$ iff for every $i$ in $\{1,2,\dots, m\}$, $S_i\subseteq S_i^{'}$.

**Addition on m-tuples.** For ${\mathcal{S}},{\mathcal{S}}^{'}\in {\mathcal{Y}}^m$ and $e\in {\mathcal{X}}$ we denote ${\mathcal{S}}\xrightarrow{\{j,e\}}{\mathcal{S}}^{'}$ whenever for every $i$ in $\{1,2,\dots, m\}$ except $j$, formally ${S^{'}_i}=S_i$ and $S^{'}_j=S_j\cup\{e\}$.

**Addition and Subtraction on m-tuples.** For ${\mathcal{S}},{\mathcal{S}}^{'}\in {\mathcal{Y}}^m$ and $e\in {\mathcal{X}}$ we denote ${\mathcal{S}}\xrightarrow[\{k,d\}]{\{j,e\}}{\mathcal{S}}^{'}$ whenever for every $i$ in $\{1,2,\dots, m\}$ except $j,k$ ${S^{'}_i}=S_i$ and $S^{'}_j=S_j\cup\{e\}$, $S^{'}_k=S_j\setminus\{d\}$.

**Discrete Derivative of Function on m-tuples.** function $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ is function that map every element of ${\mathcal{Y}}^m=\{(S_1,S_2,\dots,S_m)|\;S_i\in{\mathcal{Y}}\;\}$ to a positive number. Define the discrete derivative of $f$ at ${\mathcal{S}}\in {\mathcal{Y}}^m , e\in{\mathcal{X}}$ as follows: $$\Delta_{i,e}f(S):=f({\mathcal{S}}^{'})-f({\mathcal{S}})$$ where ${\mathcal{S}}\xrightarrow{\{j,e\}}{\mathcal{S}}^{'}$.

**Orthant-Submodularity.** Let ${\mathcal{X}}$ be finite set of elements, and ${\mathcal{Y}}=2^{\mathcal{X}}$ be the all the subset of ${\mathcal{X}}$, function $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ is function that map every element of ${\mathcal{Y}}^m=\{(S_1,S_2,\dots,S_m)|\;S_i\in{\mathcal{Y}}\;\}$ to a positive number. $f$ is **Orthant-submodular** if for every ${\mathcal{S}}$,${\mathcal{S}}^{'}\in {\mathcal{Y}}^m $ ,where ${\mathcal{S}}\leq {\mathcal{S}}^{'}$:

$$\Delta_{i,e}f({\mathcal{S}})\geq \Delta_{i,e}f({\mathcal{S}}^{'})$$

**Monotonicity.** Let ${\mathcal{X}}$ be finite set of elements, and ${\mathcal{Y}}=2^{\mathcal{X}}$ be the all the subset of ${\mathcal{X}}$, function $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ is function that map every element of ${\mathcal{Y}}^m=\{(S_1,S_2,\dots,S_m)|\;S_i\in{\mathcal{Y}}\;\}$ to a positive number. $f$ is **monotone** iff for every ${\mathcal{S}}$,${\mathcal{S}}^{'}\in {\mathcal{Y}}^m $ ,where ${\mathcal{S}}\leq {\mathcal{S}}^{'}$:

$$f({\mathcal{S}}^{'})\geq f({\mathcal{S}})$$

\[pr: monotone orthant submodular\] Consider the function $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ which is monotone and orthant-submodular. **Monotone orthant-submodular maximization with individual size constraints** is the problem of maximizing $f({\mathcal{S}})$ over m-tuples, ${\mathcal{S}}\in {\mathcal{Y}}^m$ subject to individual size constraint on every $S_i$ , formally:

\[eq:monotone orthant submodular\] $$\begin{aligned}
{3}
& \max_{\mathcal{S}}&& f({\mathcal{S}})
\label{eq:monotone orthant submodular obj}\\
&\operatorname*{subject\,\, to \quad}&& {\mathcal{S}}\in {\mathcal{Y}}^m\\
&  && |S_i| \leq k_i \;\;\;\forall i\in[m]\end{aligned}$$

\[co: equivalent of two-stage submodular\] let $f_i:{\mathcal{Y}}\xrightarrow{}{\mathbb{R}}_+$ be monotone submodular function for $i\in[m-1]$ let ${\mathcal{S}}\in {\mathcal{Y}}^m$ be ${\mathcal{S}}=(S_1,S_2,...,S_m)$ define $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ as written in \[eq: equivalent of two-stage submodular function\]: $$\label{eq: equivalent of two-stage submodular function}
    f({\mathcal{S}}):=\sum_{i=1}^{m-1} f_i(S_i\cap S_m)$$ then the function $f$ is monotone orthant-submodular. Then consider the problem which is monotone orthant-submodular maximization with individual size constraints as in \[eq: equivalent of few shot submodular optimization\] this problem has same optimal solution as problem \[pr: two-stage submodular\].

\[eq: equivalent of two-stage submodular optimization\] $$\begin{aligned}
{4}
& \max_{\mathcal{S}}&& f({\mathcal{S}})
\label{eq: equivalent of two-stage submodular optimization obj}\\
&\operatorname*{subject\,\, to \quad}&& {\mathcal{S}}\in {\mathcal{Y}}^m\\
&  && |S_i| \leq k \;\;\;\forall i\in[m-1]\\
&  && |S_m| \leq l \;\;\;\end{aligned}$$

As we saw both problem \[pr: Few-Shot Submodular optimization\] and \[pr: two-stage submodular\] are special case of monotone orthant-submodular maximization with individual size constraints. Therefore, the generalization of every meta submodular task can be formulated as maximization of monotone orthant-submodular maximization with individual size constraints.

### Algorithms for General Submodular Meta-Learning {#sec:algorithms}

### Deterministic Algorithms

In this section we will describe two greedy based algorithms that solve the problem \[pr: monotone orthant submodular\]. Note that in each algorithm we use the similar technique as in [@ohsaka2015monotone].\
In algorithm 1, we begin with $\emptyset$ for every set $S_i$ and in each step $t$ we add the pair $e$ to set $S_i$ in which $\{i,e\}$ maximize the marginal gain of $f$ and choosing $\{i,e\}$ does not violate cardinality constraints.

**Input:** a monotone orthant-submodular $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ and size constraints $k_i$ $\forall i \in [m]$\
**Output:** ${\mathcal{S}}\in {\mathcal{Y}}^m$, where $|S_i|=k_i$ $\forall i \in [m]$

Initialize $K=\sum^{m}_{i=1}k_i$ , ${\mathcal{S}}\xleftarrow[]{}\emptyset$

${\mathcal{I}}\xleftarrow[]{}\{i \in [m]\;|\;|S_i|< k_i\}$

$V_i\xleftarrow{}{\mathcal{X}}\setminus S_i$ for $i \in {\mathcal{I}}$

$\{i,e\}\xleftarrow{}  \operatorname*{arg\,max}_{ i \in {\mathcal{I}}, e\in V_i} \Delta_{i,e} f({\mathcal{S}})$ ${\mathcal{S}}\xrightarrow{\{i,e\}}{\mathcal{S}}$

**end for**

return ${\mathcal{S}}$

\[thm: main M meta convergence\] Algorithm \[alg: M meta-Greedy\] returns $\frac{1}{2}$-approximation in ${\mathcal{O}}(Kmn)$ evaluation of $f$.

### Fast Randomized Lazy Algorithm

Algorithm \[alg: M meta-Greedy\] has a high computational complexity; therefore, inspired by the idea of [@lazygreedy] we construct randomized algorithm which has lower computational complexity. The only difference is instead of choosing any element in $V_i$ we substitute a random subset of it $R_i$. This change significantly reduce the computational cost.

\[thm: Fast M meta-Greedy\] Algorithm \[alg: Fast M meta-Greedy\] returns $\frac{1}{2}$-approximation with probablity $1-\delta$ in ${\mathcal{O}}(n\,m\;logK\;log\frac{K}{\delta})$ evaluation of $f$.

**Input:** a monotone orthant-submodular $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ and size constraints $k_i$ $\forall i \in [m]$\
**Output:** ${\mathcal{S}}\in {\mathcal{Y}}^m$, where $|S_i|=k_i$ $\forall i \in [m]$

Initialize $K=\sum^{m}_{i=1}k_i$ , ${\mathcal{S}}\xleftarrow[]{}\emptyset$

${\mathcal{I}}\xleftarrow[]{}\{i \in [m]\;|\;|S_i|< k_i\}$

$V_i\xleftarrow{}{\mathcal{X}}\setminus S_i$ for $i \in {\mathcal{I}}$

$R_i\xleftarrow{}$a random subset of size $ \min\{\frac{n-|S_i|}{k_i-|S_i|}log\frac{K}{\delta},n\}$ sampled uniformly from $ V_i  $ for $ i \in {\mathcal{I}}$.

$\{i,e\} \xleftarrow{} \operatorname*{arg\,max}_{ i \in {\mathcal{I}}, e\in R_i} \Delta_{i,e} f({\mathcal{S}})$ ${\mathcal{S}}\xrightarrow{\{i,e\}}{\mathcal{S}}$

**end for**

return ${\mathcal{S}}$

### Special Example

\[co: equivalent of few shot submodular\] let $f_i:{\mathcal{Y}}\xrightarrow{}{\mathbb{R}}_+$ be monotone submodular function for $i\in[m-1]$ let ${\mathcal{S}}\in {\mathcal{Y}}^m$ be ${\mathcal{S}}=(S_1,S_2,...,S_m)$ define $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ as written in : $$\label{eq: equivalent of few shot submodular function}
    f({\mathcal{S}}):=\sum_{i=1}^{m-1} f_i(S_i\cup S_m)$$ then the function $f$ is monotone orthant-submodular. Consider the problem which is a monotone orthant-submodular maximization with individual size constraints for $f$ as in , this problem has same optimal solution as problem .

\[eq: equivalent of few shot submodular optimization\] $$\begin{aligned}
{4}
& \max_{\mathcal{S}}&& f({\mathcal{S}})
\label{eq: equivalent of few shot submodular optimization obj}\\
&\operatorname*{subject\,\, to \quad}&& {\mathcal{S}}\in {\mathcal{Y}}^m\\
&  && |S_i| \leq k-l \;\;\;\forall i\in[m-1]\\
&  && |S_m| \leq l \;\;\;\end{aligned}$$

Using Corollary \[co: equivalent of few shot submodular\] we can use algorithms for maximization of general orthant-submodular with individual size constraint, algorithm and , for discrete meta learning problem, problem . In order to do that first note that for objective function $f({\mathcal{S}}):=\sum_{i=1}^{m-1} f_i(S_i\cup S_m)$, the step 5 of algorithm can be simplified as follows. For every i and e we have: $$\Delta_{m,e} f({\mathcal{S}})=\sum_{i=1}^{m-1} f_i(S_i\cup S_m\cup{e})-f_i(S_i\cup S_m)\geq \Delta_{i,e} f({\mathcal{S}})=\ f_i(S_i\cup{e}\cup S_m)-f_i(
 S_i\cup{e}\cup S_m)$$ which means in algorithm step 5, until the $S_m$ is not hit the cardinality constraint non of the other sets have chosen. This results simplified algorithm for discrete meta learning problem. Since, algorithm .

### Convergence Analysis

### Proof of corollary \[co: equivalent of few shot submodular\]

We want to proof first that the function in equation \[eq: equivalent of few shot submodular function\] is monotone. Suppose ${\mathcal{S}}\leq {\mathcal{S}}^{'}$ we want to show $f({\mathcal{S}})\leq f({\mathcal{S}}^{'})$. we Know that every $f_i$ is monotone which means for every $j\in[m-1]$ we have $S_j\cup S_m\subseteq S_j^{'}\cup S_m^{'}$; therefore, we can conclude $f_j(S_j\cup S_m)\leq f_j(S_j^{'}\cup S_m^{'})$ which results $f({\mathcal{S}})\leq f({\mathcal{S}}^{'})$. Secondly, we want to show $\Delta_{i,e}f(S^{'})\leq \Delta_{i,e}f(S)$. let us first consider the case that $i\not = m$ then $\Delta_{i,e}f({\mathcal{S}})=f_i((\{e\}\cup S_i)\cup S_m)-f_i( S_i\cup S_m)\geq f_i((\{e\}\cup {S^{'}_i})\cup S_m^{'})-f_i( {S^{'}_i}\cup S_m^{'})=\Delta_{i,e}f({\mathcal{S}}^{'})$ follows from submodularity of $f_i$. If $i=m$ then $\Delta_{i,e}f({\mathcal{S}})=\sum_{t=1}^{m-1}f_t( S_t\cup S_m\cup \{e\})-\sum_{t=1}^{m-1}f_t( S_t\cup S_m)\geq\sum_{t=1}^{m-1}f_t( S_t^{'}\cup S_m^{'}\cup \{e\})-\sum_{t=1}^{m-1}f_t( S_t^{'}\cup S_m^{'})=\Delta_{i,e}f({\mathcal{S}}^{'})$ follows from submodularity of $f_i$.\

For proving the equivalence of two problem. First note that every feasible solution for problem \[eq: equivalent of few shot submodular optimization\] is also feasible for the maximization problem in \[eq:ML\_submodular\_sample\_avg\]. let the ${\mathcal{S}}^{*}=(S^{*}_1,S^{*}_2,\dots,S^{*}_m)$ be a maximizer of function in \[eq: equivalent of few shot submodular function\] with maximum value $OPT_1=\sum_{i=1}^{m-1} f_i(S^{*}_i\cup S^{*}_m)$, and ${\mathcal{S}}^{'}=(S^{'}_1,S^{'}_2,\dots,S^{'}_m)$ be a maximizer of problem in \[eq:ML\_submodular\_sample\_avg\] with maximum value $OPT_2=\sum_{i=1}^{m-1} f_i({S^{'}_i}\cup S^{'}_m)$, then we can conclude $f({\mathcal{S}}^*)\geq f({\mathcal{S}}^{'})$ which means $OPT_2=\sum_{i=1}^{m-1} f_i(S^{*}_i\cup S^{*}_m)\geq \sum_{i=1}^{m-1} f_i({S^{'}_i}\cup S^{'}_m)=OPT_1$. By same argument $OPT_1\geq OPT_2$, which results $OPT_1=OPT_2$.

### Proof of corollary \[co: equivalent of two-stage submodular\] 

Let the ${\mathcal{S}}^{*}=(S^{*}_1,S^{*}_2,\dots,S^{*}_m)$ be a maximizer of function in \[eq: equivalent of two-stage submodular function\] with maximum value $OPT_1=\sum_{i=1}^{m-1} f_i(S^{*}_i\cap S^{*}_m)$, and ${\mathcal{S}}^{'}=(S^{'}_1,S^{'}_2,\dots,S^{'}_m)$ be a maximizer of problem \[eq:ML\_submodular\_sample\_avg\] with maximum value $OPT_2=\sum_{i=1}^{m-1} f_i({S^{'}_i})$ . We want to show ${\mathcal{S}}^{''}:=(S^{*}_1\cap S^{*}_m ,\, S^{*}_2\cap S^{*}_m ,\,\dots,\,S^{*}_{m-1}\cap S^{*}_m,S^{*}_m)$ is a optimal solution for problem \[eq:ML\_submodular\_sample\_avg\]. Firstly, ${\mathcal{S}}^{''}$ is feasible solution for problem \[eq:ML\_submodular\_sample\_avg\]. Secondly, $OPT_1=f({\mathcal{S}}^{*})=\sum_{i=1}^{m-1} f_i(S^{*}_i\cap S^{*}_m)=\sum_{i=1}^{m-1} f_i(S^{''}_i)$ , from optimality of $S^{'}$ for problem \[eq:ML\_submodular\_sample\_avg\], $OPT_2=\sum_{i=1}^{m-1} f_i({S^{'}_i})\geq \sum_{i=1}^{m-1} f_i(S^{''}_i)=OPT_1$. Finally, observe that ${\mathcal{S}}^{'}$ is a feasible solution for \[eq: equivalent of two-stage submodular optimization\] which means $OPT_1=\sum_{i=1}^{m-1} f_i(S^{''}_i)\geq \sum_{i=1}^{m-1} f_i({S^{'}_i})=OPT_2$ results in $OPT_1=OPT_2$ .

### Proof of theorem \[thm: main M meta convergence\] {#proof: thm1}

**Incidence Matrix for m-tuples.** for m-tuple ${\mathcal{S}}$ is matrix $L({\mathcal{S}})\in {\mathbb{R}}^{n\times m}$ which define as: $$L({\mathcal{S}}):=\begin{bmatrix}
\mathbbm{1}_{S_1} & \mathbbm{1}_{S_2} &\dots& \mathbbm{1}_{S_m}
\end{bmatrix}$$

Let ${\mathcal{S}}^{(0)}=\emptyset,{\mathcal{S}}^{(1)},\dots,{\mathcal{S}}^{(t)},\dots,{\mathcal{S}}^{(K)}$ be a chain obtained by algorithm \[alg: M meta-Greedy\] and let $S^*$ be the optimal solution. Define the sequence ${\mathcal{J}}^{(0)}={\mathcal{S}}^{*},{\mathcal{J}}^{(1)},\dots,{\mathcal{J}}^{(K)}={\mathcal{S}}^{(K)}$ as follows. In step 5 of algorithm \[alg: M meta-Greedy\], we have defined $i^{(t)},e^{(t)}$ to be ..... We then define $D^{t}_{i}=J^{(t-1)}_i\setminus S^{(t-1)}_i$ and also define $o^{(t)}$ in the following way: (i) If $e^{(t)}\in D^{t}_{i^{(t)}}$, then $o^{(t)}=e^{(t)}$; (ii) Otherwise, if $e^{(t)}\notin D^{t}_{i^{(t)}}$, let $o^{(t)}$ be one of the elements of $D^{t}_{i^{(t)}}$ chosen uniformly at random. We also, define the set ${\mathcal{J}}^{(t-\frac{1}{2})}$ by deleting $o^{(t)}$ from ${\mathcal{J}}^{(t-1)}$, i.e. .... and ${\mathcal{J}}^{(t)}$ by adding $e^{(t)}$ to ${\mathcal{J}}^{(t-\frac{1}{2})}$, i.e. ...... Figure, explain how the sets.... are evolved when $t$ increases from .. to ...

\^[(0)]{}= \^[(1)]{} … \^[(t)]{} … \^[(K)]{}\
\^[(0)]{}=\^\* \^[(1)]{} … \^[(t)]{} … \^[(K)]{}

Note that by definition ${\mathcal{S}}^{(t-1)}\leq {\mathcal{J}}^{t-\frac{1}{2}}$.

\[lemma: in proof thm1\] For every $t\in [K]$ the following inequality holds: $$\label{eq:lemma_arman}
    f({\mathcal{S}}^{(t)})-f({\mathcal{S}}^{(t-1)})\geq  f({\mathcal{J}}^{(t-1)})-f({\mathcal{J}}^{(t)}).$$

Define $a^{(t)}=\Delta_{e^{(t)},i^{(t)}}f({\mathcal{J}}^{(t-\frac{1}{2})})$, and $a^{(t-\frac{1}{2})}=\Delta_{o^{(t)},i^{(t)}}f({\mathcal{J}}^{(t-\frac{1}{2})})$, and $b^{(t)}=\Delta_{e^{(t)},i^{(t)}}f({\mathcal{S}}^{(t-1)})$. We observe that $f({\mathcal{J}}^{(t-1)})-f({\mathcal{J}}^{(t)})=a^{(t-\frac{1}{2})}-a^{(t)}$. Using this notation, becomes $b^{(t)}\geq a^{(t-\frac{1}{2})}-a^{(t)}$. By monotonicity of $f$ it suffices to show $b^{(t)}\geq a^{(t-\frac{1}{2})}$. By step 5 of algorithm \[alg: M meta-Greedy\] (greedily choosing elements), we have $b^{(t)}=\Delta_{e^{(t)},i^{(t)}} f({\mathcal{S}}^{(t-1)})\geq \Delta_{o^{(t)},i^{(t)}} f({\mathcal{S}}^{(t-1)})$. Finally, by orthant-submodularity of ..., we obtain $\Delta_{o^{(t)},i^{(t)}} f({\mathcal{S}}^{(t-1)})\geq \Delta_{o^{(t)},i^{(t)}}f({\mathcal{J}}^{(t-\frac{1}{2})})=a^{(t-\frac{1}{2})}$ since ${\mathcal{S}}^{(t-1)}\leq {\mathcal{J}}^{t-\frac{1}{2}}$.

Finally, by summing over the relations , we obtain: $$\begin{aligned}
  f_{final}-0= f({\mathcal{S}}^{(K)})-f({\mathcal{S}}^{(0)})&=\sum_{t=1}^{t=K} f({\mathcal{S}}^{(t)})-f({\mathcal{S}}^{(t-1)})\geq     \sum_{t=1}^{t=K}f({\mathcal{J}}^{(t-1)})-f({\mathcal{J}}^{(t)})
   \\&=f({\mathcal{J}}^{(K)})-f({\mathcal{J}}^{(0)})= f_{final}-OPT\end{aligned}$$

### Proof of theorem \[thm: Fast M meta-Greedy\]

We reruse the notation $i^{(t)},e^{(t)},{\mathcal{J}}^{(t)},{\mathcal{S}}^{(t)},D_i^t$ in section \[proof: thm1\]. Assume $R_i^{(t)}$ be the $R_i$ in $t^{th}$ iteration. Let us iteratively define ${\mathcal{J}}^{(0)}={\mathcal{S}}^{*},{\mathcal{J}}^{(1)},\dots,{\mathcal{J}}^{(m)}={\mathcal{S}}^{(K)}$ as follows. If $R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t}$ is empty, then algorithm fails if not set $o^{(t)}=e^{(t)}$ if $e^{(t)}\in R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t} $ or if $e^{(t)}\not\in R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t} $ set $o^{(t)}$ a random element from $R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t}$. Every other part of the proof follows as in section \[proof: thm1\]. We just need to find the probability that the algorithm fails.

With probability $1-\delta$ , $R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t}\not = \emptyset$ for every $t\in [K]$.

If for any $t\in [K]$ $|R_{i^{(t)}}^{t}|=n$ then $Pr[R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t}=\emptyset]=0$ $$\begin{aligned}
    Pr[R_{i^{(t)}}^{t}\cap D_{i^{(t)}}^{t}=\emptyset]&=(1-\frac{|S_{i^{(t)}}^{t}|}{|V_{i^{(t)}}^t|})^{(|R_{i^{(t)}}^{t}|)}=(1-\frac{k_{i^{(t)}}-|S_{i^{(t)}}^{t-1}|}{n-|S_{i^{(t)}}^{t-1}|})^{(|R_{i^{(t)}}^{t}|)}\\&\leq exp({-(\frac{k_{i^{(t)}}-|S_{i^{(t)}}^{t-1}|}{n-|S_{i^{(t)}}^{t-1}|}) (\frac{n-|S_{i^{(t)}}^{t-1}|}{k_{i^{(t)}}-|S_{i^{(t)}}^{t-1}|})log(\frac{K}{\delta})})=\frac{K}{\delta}\end{aligned}$$ union bound over $t\in [K]$ prove the lemma.

Algorithm for Worst Case Setting {#sec: Distribution Agnostic Algorithm}
--------------------------------

In the first section, we discussed the proper formulation for the case that we aim to choose an initial subset of the desired set at the training time and the remaining elements at the test time. In particular, we introduced the formulation that finds the best initial set that in expectation or on average would perform well when we later add the best subset to it. Indeed, this formulation leads to a good generalization result since we assume all tasks at the training time are drawn from a common distribution and the task that we observe at the test time is also drawn from that distribution.

However, in some cases, either the tasks in the training phase are not necessarily drawn from the same distribution, or instead of average performance we care about the worst-case performance. In either case, instead of measuring the performance of the initial set in terms of the maximum value of the expected objective function, we aim to maximize the minimum objective function value over all given tasks. In other words, we aim to solve $$\label{eq:ML_submodular_minmax}
    \max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \min_{i=1,\dots, m}\;  \max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)
   \ = \ \max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \min_{i=1,\dots, m}\;   f_i'({S_{\rm{tr}}}).$$ Note that both problems in are equivalent since $f_i'({S_{\rm{tr}}}):=\max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)$. Later, in Section \[sec:algorithms\_ML\] we formally present efficient methods for solving this problem and characterize their theoretical guarantees.

### Equivalent of Worst Case Setting

\[co: equivalent of MASML\] let $f_i:{\mathcal{Y}}\xrightarrow{}{\mathbb{R}}_+$ be monotone submodular function for $i\in[m]$ let ${\mathcal{S}}\in {\mathcal{Y}}^{m+1}$ be ${\mathcal{S}}=(S_1,S_2,...,{S_{\rm{tr}}})$ define $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$ as written in : $$\label{eq: equivalent of MASML function}
    f({\mathcal{S}}):=\min_{i\in [m]} f_i(S_i\cup {S_{\rm{tr}}})$$ Then consider the problem which is a maximization of $f$ with individual size constraints as in \[eq: equivalent of MASML\], this problem has same optimal solution as problem .

\[eq: equivalent of MASML\] $$\begin{aligned}
{4}
& \max_{\mathcal{S}}&& f({\mathcal{S}})
\label{eq: equivalent of MASML obj}\\
&\operatorname*{subject\,\, to \quad}&& {\mathcal{S}}\in {\mathcal{Y}}^{m+1}\\
&  && |S_i| \leq k-l \;\;\;\forall i\in[m]\\
&  && |{S_{\rm{tr}}}| \leq l \;\;\;\end{aligned}$$

### Proof of corollary \[co: equivalent of MASML\]

For proving the equivalence of two problem. First note that every feasible solution for problem in \[eq: equivalent of MASML\] is also feasible for the maximization problem in . let the ${\mathcal{S}}^{*}=(S^{*}_1,S^{*}_2,\dots,S^{*}_{tr})$ be a maximizer of function in \[eq: equivalent of MASML\] with maximum value $OPT_1=\min\limits_{i\in [m]} f_i(S^{*}_i\cup S^{*}_{tr})$, and ${\mathcal{S}}^{'}=(S^{'}_1,S^{'}_2,\dots,S^{'}_{tr})$ be a maximizer of problem with maximum value $OPT_2=\min\limits_{i\in [m]} f_i({S^{'}_i}\cup S^{'}_{tr})$, then we can conclude $OPT_1\geq \min\limits_{i\in [m]} f_i(S_i\cup S_m)$ for every ${\mathcal{S}}$ in feasible set specially ${\mathcal{S}}={\mathcal{S}}^{'}$ which results $OPT_1\geq OPT_2$. Similarly, $OPT_2=\min\limits_{i\in [m]}\max\limits_{S_i}f_i({S_{\rm{tr}}}^{*}\cup S_i)\geq\min\limits_{i\in [m]}\max\limits_{S_i}f_i({S_{\rm{tr}}}^{'}\cup S_i)\geq\min\limits_{i\in [m]}f_i({S_{\rm{tr}}}^{'}\cup {S^{'}_i})=OPT_1$.

\[co: Hardness of MASML\] Finding any constant factor of problem in is NP-Hard. Because, even in the case of $m=1$ the problem is equivalent to robust submodular optimization which is NP-Hard to find any constant approximation factor.

### Bi-criteria Approximation Algorithm

It is computationally hard to find the approximation solution for problem in \[eq: equivalent of MASML\]. Therefore, we try to solve the problem with Bi-criteria Approximation method. First, Using slack variable $c$ we can reformulate the \[eq: equivalent of MASML\] as \[eq MASML equal slack variable\].

\[eq MASML equal slack variable\]$$\begin{aligned}
{4}
& \max_{{\mathcal{S}},c} && c
\label{eq: MASML equal slack variable obj}\\
&\operatorname*{subject\,\, to \quad}&& f_i(S_i\cup {S_{\rm{tr}}})\geq c\\
&  && {\mathcal{S}}\in {\mathcal{Y}}^{m+1}\\
&  && |S_i| \leq k-l &&&\forall i\in[m]\\
&  && |{S_{\rm{tr}}}| \leq l \;\;\;\end{aligned}$$

Then, inspired by [@krause2008robust] we relaxed the cardinality constraints in \[eq MASML equal slack variable\] which results \[eq: Relaxed MASML2\].

\[eq: Relaxed MASML2\] $$\begin{aligned}
{4}
& \max_{{\mathcal{S}},c} && c
\label{eq: Relaxed MASML2 obj}\\
&\operatorname*{subject\,\, to \quad}&& f_i(S_i\cup {S_{\rm{tr}}})\geq c \;\;\;&&&\forall i\in[m]\label{eq: Relaxed MASML2 const1}\\
&  && {\mathcal{S}}\in {\mathcal{Y}}^{m+1}\label{eq: Relaxed MASML2 const2}\\
&  && |S_i| \leq \alpha (k-l) &&&\forall i\in[m]\label{eq: Relaxed MASML2 const3}\\
&  && |{S_{\rm{tr}}}|  \leq \alpha l\label{eq: Relaxed MASML2 const4} \;\;\;\end{aligned}$$

Our goal is approximately solve \[eq: Relaxed MASML2\]. In order to do that we will use binary search procedure over c, by itertaively solving \[eq: Relaxation Binary Search Procedure\] and make the search interval smaller in each step. We can reformulate and relax the constraints in \[eq: Relaxed MASML2 const1\]-\[eq: Relaxed MASML2 const4\] as \[eq: Relaxation Binary Search Procedure const1\]-\[eq: Relaxation Binary Search Procedure const3\].

\[eq: Relaxation Binary Search Procedure\] $$\begin{aligned}
{4}
& {\mathcal{S}}_c^{*}=\operatorname*{arg\,min}_{{\mathcal{S}}} && \mid {\mathcal{S}}\mid = \sum_{i=1}^{m} \mid S_i \mid+\mid {S_{\rm{tr}}}\mid
\label{eq: Relaxation Binary Search Procedure obj}\\
&\operatorname*{subject\,\, to \quad}&& F_c({\mathcal{S}}):=\frac{1}{m}\sum_{i=1}^{m}\min\{f_i(S_i\cup {S_{\rm{tr}}}),c\}= F_c({\mathcal{X}}^{m+1}) \;\;\label{eq: Relaxation Binary Search Procedure const1}\\
&  && {\mathcal{S}}\in {\mathcal{Y}}^{m+1}\\
&  && \frac{\mid S_i \mid}{\mid {\mathcal{S}}\mid} \leq \frac{(k-l)}{(k-l)(m)+l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \forall i\in[m]\label{eq: Relaxation Binary Search Procedure const2}\\
& && \frac{\mid {S_{\rm{tr}}}\mid}{\mid {\mathcal{S}}\mid} \leq \frac{l}{(k-l)(m)+l}  \label{eq: Relaxation Binary Search Procedure const3}\end{aligned}$$

We named the optimal value of problem $Z=\min \mid{\mathcal{S}}^{*}_c\mid$. The bi-criteria approximation procedure start with $c_{min}=0$ , $c_{max}=\min_if_i({\mathcal{X}})$ and In each step solves optimization problem in \[eq: Relaxation Binary Search Procedure\] by algorithm \[alg: meta-Saturation Submodular algorithm \]and give us the solution ${\mathcal{S}}^{*}_{c}$ and update $c_{min}$ , $c_{max}$ as follows.

-   if $ \mid {\mathcal{S}}^{*}_{c} \mid :=\sum\limits_{i=1}^{m} \mid S_i^{c} \mid +\mid {S_{\rm{tr}}}^{c} \mid\; \geq \; \alpha (l+(m)(k-l))$ or the problem was infeasible then $c_{max}=c$

-   if $ \mid {\mathcal{S}}^{*}_{c} \mid =\sum\limits_{i=1}^{m} \mid S_i^{c} \mid+\mid {S_{\rm{tr}}}^{c} \mid \; \leq \; \alpha (l+(m)(k-l))$ then $c_{min}=c$

\[eq: Relaxation Binary Search Procedure\] $$\begin{aligned}
{4}
& {\mathcal{S}}_c^{*}=\operatorname*{arg\,min}_{{\mathcal{S}}} && \mid {\mathcal{S}}\mid = \sum_{i=1}^{m} \mid S_i \mid +\mid {S_{\rm{tr}}}^{c} \mid
\label{eq: Relaxation Binary Search Procedure obj}\\
&\operatorname*{subject\,\, to \quad}&& f_i(S_i\cup {S_{\rm{tr}}})\geq c \;\;&&&\;\; \forall i\in[m]\\
&  && {\mathcal{S}}\in {\mathcal{Y}}^m\\
&  && \frac{\mid S_i \mid}{\mid {\mathcal{S}}\mid} \leq \frac{k}{k(m)+l} &&&\;\; \forall i\in[m]\\
& && \frac{\mid {S_{\rm{tr}}}\mid}{\mid {\mathcal{S}}\mid} \leq \frac{l}{k(m)+l} &&&\;\; \end{aligned}$$

**Input:** a function $f:{\mathcal{Y}}^{m+1}\xrightarrow{}{\mathbb{R}}_+$ ,c , ${\mathcal{S}}^0=\emptyset$, $t=0$\
**Output:** ${\mathcal{S}}\in {\mathcal{Y}}^m$

${\mathcal{I}}\xleftarrow[]{}\{i \in [m]\;|\; i\; $satisfy \[eq: Relaxation Binary Search Procedure const2\] and \[eq: Relaxation Binary Search Procedure const3\]$ \}$ ${\mathcal{I}}=\{tr\}$$V_i\xleftarrow{}{\mathcal{X}}\setminus S_i$ for $i \in {\mathcal{I}}$

$\{i^t,j^t\} \xleftarrow{} \operatorname*{arg\,max}_{ i \in {\mathcal{I}}, j\in V_i} \Delta_{i,j} f({\mathcal{S}}^t)$ ${\mathcal{S}}^t \xrightarrow{\{i^t,j^t\}}{\mathcal{S}}^{t+1}$, $\theta^{t}:=\;\frac{1}{\Delta_{i^{t},j^{t}}F_c({\mathcal{S}}^{t})}$ , $t \xleftarrow{}t+1$ **end While**

return ${\mathcal{S}}$

In the following lemma we analyze the quality of solution for each run of the greedy algorithm.

\[eq: model agnostic main lemma \] For integral valued $f_i$ and feasible c Algorithm \[alg: M meta-Greedy submodular partial cover (MGPC)\] finds m tuple ${\mathcal{S}}^{G}$ which $f_i({\mathcal{S}}^{G})\geq c$ for all $i$ and $\mid S_i^{G}\mid\leq \alpha \mid S_i^{*} \mid$ where ${\mathcal{S}}^{*}$ is optimal solution and $\alpha=1 +log(max_{e\in{\mathcal{X}},i\in[m]}\Delta_{i,e}f(\emptyset))$.

**Sketch of the proof:**\
Our proof is similar to the proof in [@wolsey1982analysis]. We want to find upper bound on the greedy solution provided by Algorithm \[alg: M meta-Greedy submodular partial cover (MGPC)\] for optimization problem . To do that, we propose some related problems( , and ) that leads us to find a upper bound. First, we propose problem which is equivalent to . This equivalency will be proven in corollary . Then, we relaxed two constraints , and in and provide a upper bound for solution in . In particular, if $Z^L$ is the optimal value of ,then $Z^L\leq Z$. Afterward, using duality we argue that if $D^L$ is the optimal value of dual problem of we have $Z^L\geq D^L$. Finally, we show that if $Z^G$ is the value of for solution of algorithm  we have $D^L\geq Z^G(\alpha)^{-1}$ in lemma \[lemma: final in proof of MASMAl1\] and \[lemma: final in proof of MASMAl2\]. In nutshell, we proved lemma \[eq: model agnostic main lemma \] by showing: $$Z\geq Z^L\geq D^L\geq Z^G(\alpha)^{-1}$$ where $Z$ is the optimal value of , $Z^G$ is the value of for solution of algorithm , $Z^L$ is the optimal value of , and $D^L$ is the optimal value of dual problem of .

\[col: MASML1\] We will propose the problem which is equivalent to and have same optimal value. For any m-tuple ${\mathcal{S}}$ which is feasible for let it is indicator matrix $z$ be a matrix in which for every $i\in [m]$ and $j \in [n]$, $z_{i,j}={\mathbf{1}}\{j\in S_i\}$ and let $f_i^c(S)=\min\{c,f_i(S)\}$. Then, $z$ is feasible for and the optimal value of two problem is same. (the argument is similar to proposition 2 in [@wolsey1982analysis] ).

\[eq: Relaxation LP\] $$\begin{aligned}
{4}
& Z=\min_{z} && \sum_{i=1}^{m}\sum_{j=1}^{n}  z_{i,j} 
\label{eq: LPRelaxation}\\
&\operatorname*{subject\,\, to \quad}&& \sum_{i=l,m}\sum_{j=1}^{n} \Delta_{i,j} f_{i}^{c} (S_{l}\cup {S_{\rm{tr}}})z_{i,j} \geq -f_i^c(S_{l}\cup {S_{\rm{tr}}})+f_i^c({\mathcal{X}})\notag \label{eq:Relaxation LP eq1}\\
&  && \;\;\;\;\;\;\quad\;\forall t=0,\dots,T-1 \;,\; l\in [m] \;,\;\forall {\mathcal{S}}\in{\mathcal{Y}}^m\\
&  && z_{i,j} \in \{0,1\}\\
&  && \frac{\sum_{j=1}^{n}  z_{i,j} }{\sum_{i=1}^{m}\sum_{j=1}^{n}  z_{i,j} } \leq \frac{k}{k(m)+l} &&&\;\; \forall i\in[m]\label{eq:Relaxation LP eq3}\\
& && \frac{\sum_{j=1}^{n}  z_{m,j} }{\sum_{i=1}^{m}\sum_{j=1}^{n}  z_{i,j} } \leq \frac{l}{k(m)+l} &&&\label{eq:Relaxation LP eq4}\;\; \end{aligned}$$

The equivalency of and is direct result of the proposition 2 in [@wolsey1982analysis].

let $\theta^{t}$ be the output of algorithm \[alg: M meta-Greedy submodular partial cover (MGPC)\] for $t=0,1,\dots T$ where $T$ is number of iteration of algorithm \[alg: M meta-Greedy submodular partial cover (MGPC)\]. we will prove $\mid S_i^{G}\mid\leq \alpha \frac{l}{k(m)+l} \mid {\mathcal{S}}^{*} \mid=\alpha  \mid {\mathcal{S}}_i^{*} \mid$. To show that let us define $Z^l$ as follows:

\[eq: Relaxation LP2\] $$\begin{aligned}
{4}
& Z^{L}=\min_{z} && \sum_{i=1}^{m}\sum_{j=1}^{n}  z_{i,j} 
\label{eq: LPRelaxation2}\\
&\operatorname*{subject\,\, to \quad}&& \sum_{i=l,m}\sum_{j=1}^{n} \Delta_{i,j}f_i^c({S_{\rm{tr}}}^t\cup {S_{\rm{tr}}}^t)z_{i,j} \geq -f_i^c({S_{\rm{tr}}}^t\cup {S_{\rm{tr}}}^t)+f_i^c({\mathcal{Y}}) \notag\\ \; \; & &&\;\; \forall t=0,\dots,T-1 \;,\; l\in [m]\\
&  && z_{i,j} \geq 0\end{aligned}$$

This problem relaxed two constraints , and in and as consequence $Z^L\leq Z$. Then, Let $D^L$ be the optimal value of dual problem of . Then, by weak duality $D^L\leq Z^L$.

\[lemma: final in proof of MASMAl1\] Let us call the final value of Algorithm \[alg: M meta-Greedy submodular partial cover (MGPC)\] $Z^G$, and let $\bar f_{i^t}^c(S):=\sum\limits_{i=1}^m f_{i}^c(S){\mathbf{1}}\{i=i^t\; or\; i^t=tr\} $ .Then, we can write $Z^G$ as follows. $$Z^G =\sum_{t=1}^{T}\theta^{t} (F_c({\mathcal{S}}^{t})-F_c({\mathcal{S}}^{t-1}))=\theta^1(\bar f_{i^1}^c({\mathcal{X}}))+\sum_{t=1}^{T}(\theta^{t}-\theta^{t-1})(\bar f_{i^t}^c({\mathcal{X}})-F_c({\mathcal{S}}^{t-1}))$$ First Inequality is a direct consequence of definition of $\theta^t $ and by rearranging and add and subtract $\bar f^c_i({\mathcal{X}})$ we get the second equality.

\[lemma: final in proof of MASMAl2\] Let $D^L$ be optimal value of dual problem of . We can find following lower bound for $D^L$. $$D^L\geq(\theta^1(f_{i^1}^c({\mathcal{X}}))+ \sum_{t=1}^{T}(\theta^{t}-\theta^{t-1})(\bar f_{i^t}^c({\mathcal{X}})-F_c({\mathcal{S}}^{t-1})))(\alpha)^{-1}$$ First for every $j\in {\mathcal{X}}$ there exist $r\leq T$ that $(\Delta_{i^t,j}F_c({\mathcal{S}}^{r-1}))>0$ and $(\Delta_{i^t,j}F_c({\mathcal{S}}^{r}))=0$ . We want to prove $\alpha^{-1}\theta^*$ is dual feasible where $\theta^*=(\theta^1{\mathbf{1}}_{i^0},(\theta^2 -\theta^1){\mathbf{1}}_{i^1},\dots (\theta^T-\theta^{T-1}){\mathbf{1}}_{i^{T-1}})\in {\mathbb{R}}^{(m)\times T }$ (${\mathbf{1}}_{i}$ is vector of size $m$ which is 1 in the $i^{th}$ place or if $i=tr$ it is all ones) for every $j$ we have the following. $$(\theta^1(f_{i^1}^c({\mathcal{X}}))+ \sum_{t=1}^{T}(\theta^{t}-\theta^{t-1})(\Delta_{i^t,j}F_c({\mathcal{S}}^t))\leq 
 (\max_{t=1,...,r} (\theta^{t})(\Delta_{i^t,j}F_c({\mathcal{S}}^t))) (\alpha)\leq \alpha$$ The first inequality follows from proposition 3 in [@wolsey1982analysis] and $(\theta^{t})(\Delta_{i^t,j}F_c({\mathcal{S}}^t))\leq1$ is consequence of definition of $(\theta^{t})$ and the fact that $i^t$ chosen greedily. Therefore, $\alpha^{-1}\theta^*$ is dual feasible and we can write the . $$\label{eq: dual LPR}
 (\theta^1(f_{i^1}^c({\mathcal{X}}))+ \sum_{t=1}^{T}(\theta^{t}-\theta^{t-1})(\bar f_{i^t}^c({\mathcal{X}})-F_c({\mathcal{S}}^{t-1}))) (\alpha^{-1})\leq D^L$$

Then, combing all we have:

$$Z\geq Z^L\geq D^L\geq(\theta^1(f_{i^1}^c({\mathcal{X}}))+ \sum_{t=1}^{T}(\theta^{t}-\theta^{t-1})(\bar f_{i^t}^c({\mathcal{X}})-F_c({\mathcal{S}}^{t-1})))(\alpha)^{-1}=Z^G(\alpha)^{-1}$$

which resualts $\mid S_i^{G}\mid\leq \alpha \frac{l}{k(m)+l} Z=\alpha  \mid {\mathcal{S}}_i^{*} \mid$.

In algorithm \[alg: meta-Saturation Submodular algorithm \], we present the whole procedure for finding solution for worst case setting.

**Input:** a function $f:{\mathcal{Y}}^m\xrightarrow{}{\mathbb{R}}_+$\
**Output:** ${\mathcal{S}}\in {\mathcal{Y}}^m$

$c\xleftarrow[]{}\frac{c_{max}+c_{min}}{2}$

$\Tilde{{\mathcal{S}}}=MGPC(F_c,c)$

$c_{max}\xleftarrow[]{}c$ $c_{min}\xleftarrow[]{}c$ , ${\mathcal{S}}_{best}\xleftarrow[]{}\Tilde{{\mathcal{S}}}$ **end While**

return ${\mathcal{S}}_{best}$

The following theorem prove that the optimal value of worst case setting can be achieve by algorithm \[alg: meta-Saturation Submodular algorithm \] if we relax the conditions as follows.

for any $k,l$ algorithm \[alg: meta-Saturation Submodular algorithm \] find m-tuple ${\mathcal{S}}^{'}$ where $$\min_i f_i(S_i^{'}\cup {S_{\rm{tr}}}^{'})\geq  \max_{{\mathcal{S}}}\min_i f_i(S_i\cup {S_{\rm{tr}}})$$ and $\mid S_i^{'}\mid\leq \alpha (k-l)$ for $i\in[m]$ and $\mid {S_{\rm{tr}}}^{'}\mid\leq \alpha l$.

In each step $\mid {\mathcal{S}}_{best}\mid \leq \alpha( l+ (m)(k-l))$ and $c^{*}\in [c_{min}, c_{max})$. Since, $f_i$ are integer, and $c_{max}-c_{min}< \frac{1}{m}$; we can conclude $\min\limits_i f_i(S_i^{'}\cup {S_{\rm{tr}}}^{'})\geq  \max\limits_{{\mathcal{S}}}\min\limits_i f_i(S_i\cup {S_{\rm{tr}}})$.

Simulation supplementary
------------------------

### Ride Share Optimization

In this application, we try to solve facility location problem on Uber dataset [@uber_2019]. One part of this dataset, that we work with consists of the September 2014 Uber pick-ups in Manhattan, which is around 1,000,000 data point, each one in the form of $(latitude, longitude, datatime)$. Our goal is to use the data from the past to find the better waiting location for drivers in the future. In particular, We want to find subset of location that minimizes the defined metric between each customers to his closest driver. To be more precise, given a customer $p=(x_p,y_p)$ and driver $r=(x_r, y_r)$ define a manhatan distance between these two point as $d(p,r)=|x_p-x_r|+|y_p-y_r|$. We use the same metric as [@mitrovic2018data], the “convenience score”, which is $c(p,r)=2-\frac{2}{1+e^{-200 d(p,r)}}$.Next, let us define the tasks and learning procedure more clearly. We use September 1 of 2014 as a training set and September 2 of 2014 as a test set. September 1 of 2014 consists of around 700 points and September 1 of 2014 consists of around 1200 points. We define a Time slot $T_a$ by selecting point $a$ and pick 10 data points in half an hour before point $a$ and for each one pick 10 points in 1 km neighborhood of that which makes a total of 100 points. Each task is ${\mathcal{T}}_a=\{\ f_a,T_a\}$ where $f_a$ is monotone submodular function defined for every driver waiting locations set $S$ as $f_a(S)=\sum_{p\in T_a}\max_{r\in S}c(p,r)$, and $T_a$ is corresponding time slot set. We pick 100,000 points at random from the September 2014 Uber pick-ups locations as ground set. For training we pick $m$ points at random from the first week $a_1,a_2,\dots, a_m$ and consider the tasks ${\mathcal{T}}_1, {\mathcal{T}}_2,\dots,{\mathcal{T}}_m$. We run the **Greedy Train**(running greedy at training on sum),**meta-Greedy**, and **Random meta-Greedy** algorithms on them which means we try to optimize $\sum_{i=1}^{m}f_{a_{i}}({S_{\rm{tr}}}\cup S_i)$ and find set $S$ with size $l$ which can be used in test time as initial set. In test time we test the performance of algorithms on the series of tasks ${\mathcal{T}}^{'}_{1}, {\mathcal{T}}^{'}_{2},\dots,{\mathcal{T}}^{'}_{h}$ and report the comparison of performance on average. First, we pick $m$ points at random from second week $a^{'}_{1}, a^{'}_{2},\dots,a^{'}_{m}$ and look at the performance of the **Greedy Train**,**Greedy Test**,**meta Greedy**, and **random meta Greedy** algorithms on this tasks. We report the normalized performance of algorithms in figure \[fig:simulation-ride\]. We can see if we run greedy for each task in test time independently, we achieve better performance, but in the price of computation time.

### Movie Recommendation

In this application we use the data set of movies from movielens dataset [@fivethirtyeight_2019]. The data set consists of movie information and movie ratings between 1 to 5. We pick the subset of 2000 most rated movies and 200 user that rate the highest to these movies same as [@stan2017probabilistic]. Each movies can belong to 18 genres(Horror, Thriller, and etc.). We define a set of all movies in genre $t$ as $G_t$ and define $R_i$ be the set of all movie rated by user $i$, in which for each movie $v \in R_i$, $r_i(v)$ is a corresponding rating. Here we define a user based task which involves 5 users ratings and the related objective functions; formally ${\mathcal{T}}_j=\{ \{f_{j_i}\}_{i=1}^{5},\{R_{j_i}\}_{i=1}^{5}\}$ which $f_{j_i}$ is monotone submodular function and $R_{j_i}$ is set of movie ratings by user $j_i$. In particular, we define $f_i$ as in equation . $$\label{eq: mov recom obj2}
    f_i(S)=\sum_{t=1}^{18}  w_{i,t}.\max_{v\in R_i\cap G_t \cap S} r_i(v)$$ which is the weighted average over maximum rate that user $i$ gives to movies from each genre and $w_{i,t}$ is proportion of movies in genre $t$ which is rated by user $i$ out of all the rating he provides. We divide 200 users to two parts the first 100 users for training, and the second 100 users for test. We show the results in figure \[fig:simulation-movrecom\]. As we can see the performance of meta-Greedy is really close to Greedy test while it is faster. For example, in simulation of Figure the average time for Greedy test algorithm is 4.33 sec per running, and meta-Greedy is 0.91 sec per running while the performance of meta-greedy is close to Greedy test.

Counter-example for Submodularity of the Objective in  {#sec:counter_example}
======================================================

In this section, we provide a counterexample for submodularity of the objective function in the equation . We consider a maximum coverage problem in which the function value is an area covered by a set of elements. We define the ground set $V=\{ABIJ,BCDI,ACDJ,IDEH\\,HEFG,BCEH\}$ which has shown in Figure \[fig:Counter Example\]. Each element is a rectangle, and a function value of that element is an area covered by that element. We refer to each element (rectangle) by it’s vertices.

Let $AC=CD=DE=EF=1$, and $BC=0.75$. Also in we let $m=1$ and $k-l=1$ which means that we are considering a single set function $f$ defined as: $f(S)=\max_{e \in V} A(S\cup e)$, where $A(T)$ is a area of set $T$. Note that the area function $A$ is monotone and submodular, however as we will show below, the function $f$ is not submodular. To do so, we consider two sets $T_1=\emptyset$ and $T_2=\{ACDJ\}$ and add the element $IDEH$ to both sets and observe that $f$ does not satisfy the diminishing returns property. Let us first compute the function value at $T_1$ and $T_2$ as follows: $$f(T_1)=\max_{e \in V} A(e)=A(\{BCEH\})=1.5,$$ and $$f(T_2)=\max_{e \in V} A(T_2\cup e)=A(\{ACDJ,IDEH\})=1.75.$$ Similarly, we compute the function value at $T_1^{'}=T_1\cup \{IDEH\} $, and $T_2^{'}=T_2\cup \{IDEH\} $: $$f(T_1^{'})=\max_{e \in V} A(T_1^{'}\cup e)=A(\{IDEH,ACDJ\})=1.75,$$ and $$f(T_2^{'})=\max_{e \in V} A(T_2^{'}\cup e)=A(\{IDEH,ACDJ,EFGH\})=2.5.$$ We can now see that $T_1\subseteq T_2$, but $f(T_2^{'})-f(T_2)\not \leq f(T_1^{'})-f(T_1)$. Therefore, $f$ is not submodular.

Also let us make a remark about $k$-submodularity which studies functions of $k$ subsets of the ground set that are disjoint sets. This class of functions is submodular in each orthant [@ohsaka2015monotone]. However, in the submodular meta-learning framework, sets can have overlap, and there is no restriction on the sets to be disjoint. Therefore, our framework is different from $k$-submodular maximization.

                            Objective Value  
  ------------------------ ----------------- --
  Greedy-Train                 0.896822      
  Greedy-Test                  0.963639      
  Random                       0.839599      
  Meta-Greedy                  0.949555      
  Randomized Meta-Greedy       0.945020      
  Replacement Greedy           0.910977      

  : Comparison of two-stage framework and submodular meta-learning framework

### Two-Stage Submodular Meta-Learning

Although, our submodular meta-learning has the ability of personalizing the solution in test time but it is still use the same ${S_{\rm{tr}}}$ for every task. But learning all the set ${S_{\rm{tr}}}\cup S_i$ is computationally expensive in the test time. Therefore, we need to find the way to personalize ${S_{\rm{tr}}}$ too without increasing the computational power. In order to that, we come up with following approach: Let assume similar to two-stage framework we learn reduced ground set in. training but instead of choosing the. whole set as a subset of this set instead we just choose ${S_{\rm{tr}}}$ as subset of this set and we let $S_i$ be personalized at the test time. Formally, we try to solve the following problem:

\[eq:two-stage sub meta-learning\] $$\begin{aligned}
{4}
& \max_{S,\tilde{S_i}} && \sum_{i=1}^{m}\; \max_{\mid S_i\mid \leq k-l}\; f_i(S_i\cup \tilde{S_i})
\label{eq: LPRelaxation2}\\
&\operatorname*{subject\,\, to \quad}&&\tilde{S_i}\subseteq S\\ \; \; 
& &&\mid \tilde{S_i}\mid \leq l\;\;\\ 
&  &&\mid S\mid \leq q\;\;\\ \end{aligned}$$

Note that the optimal value of this problem is higher than related two-stage submodular maximization and related meta-submodular maximization problem; since, if $q=l$ this problem reduced to meta-submodular problem and if $k=l$ this problem reduced to two-stage submodular maximization.

### Two-Stage Submodular Meta-Learning Algorithm

For solving the problem \[eq:two-stage sub meta-learning\] the natural way that come to mind is to some how combining the replacement greedy algorithm and meta-Greedy algorithm but how we can do that? One way to doing that is to fill $S_i$ greedily and then using the replacement greedy to obtain $S,\tilde{S_i}$ then we can use $S$ as reduced ground set in test time.

**Initialize** ${S_{\rm{tr}}}=\{S_i\}_{i=1}^m=\{\tilde{S}_i\}_{i=1}^m=\emptyset$ Find $e_i^{*} =  \operatorname*{arg\,max}_{ e\in V}  \Delta_i(e|S_i)$ $S_i\xleftarrow{} S_i\cup\{e_i^{*}\}$ **end for** **end for** Find $ e^{*} =\!\operatorname*{arg\,max}_{ e\in V} \!\sum\limits_{i=1}^{m}\!\nabla_{i}(e|\tilde{S_i} \cup S_i)$ $S\xleftarrow{} S\cup\{e^{*}\}$ $\tilde{S_i}\xleftarrow{} \tilde{S_i}\cup\{e^{*}\}\setminus \text{REP}_i(e^{*},\tilde{S_i})$ **end for**

Return $\tilde{S_i}$, $S$ and $S_i$

In the above algorithm $\nabla_{i}(e|S)=\Delta_i(e|S)$ if $\mid S\mid\not=l $, and $\nabla_{i}(e|S)=\max\{0,\max_{x \in S}{\nabla_i{(e,x,S)}}\}$, and $\text{REP}_i(e,S)=\operatorname*{arg\,max}_{x \in S}{\nabla_i{(e,x,S)}}$ if $\mid S\mid=l $ and is $\emptyset$ if $\mid S\mid\not=l $. Finally, $\nabla_i{(e,x,S)}=f_i(e\cup S\setminus x)-f_i(S)$.

### Analysis of Two-Stage submodular Meta-Learning Algorithm

First suppose $S_i$ and $\tilde{S_i}$ and $S$ is a output of algorithm \[alg: two-stage meta-Greedy\]; because, the first phase of algorithm \[alg: two-stage meta-Greedy\] is same as first phase of algorithm \[alg: Reverse discrete meta-Greedy\] we can have the same analysis as the one for which results:

$$\label{eq: two-stage eq1 pf}
    \sum_{i=1}^m f_i(\tilde{S_i}^{*} \cup S_i^{*}) - \sum_{i=1}^m f_i( S_i)\leq  \sum_{i=1}^m f_i(\tilde{S_i}^{*} \cup S_i)$$

Also by analysis of replacement greedy in [@stan2017probabilistic], we can obtain the following: $$\begin{aligned}
 \sum_{i=1}^m f_i(\tilde{S_i}\cup S_i)-f_i( S_i)&\geq \frac{1}{2}(1-\frac{1}{e^2})(\sum_{i=1}^m f_i(\tilde{S_i}^{opt}\cup S_i)-f_i(S_i))
\label{eq: eq3 pf two-stage} \\&\geq  \frac{1}{2}(1-\frac{1}{e^2})(\sum_{i=1}^m f_i(\tilde{S_i}^{*}\cup S_i)-f_i(S_i))
 \label{eq: eq3 pf two-stage }\\&\geq  \frac{1}{2}(1-\frac{1}{e^2})(\sum_{i=1}^m f_i(\tilde{S_i}^{*}\cup S_i^{*})-2f_i(S_i))
\label{eq: eq3 pf two-stage}\end{aligned}$$ Also $S_i\subseteq S_i\cup \tilde{S_i}$ and monotonicity $\sum_{i=1}^m f_i(\tilde{S_i}\cup S_i)\geq \sum_{i=1}^m f_i( S_i)$. therefore, if we let $\theta=\sum_{i=1}^m f_i( S_i)$: $$\sum_{i=1}^m f_i(\tilde{S_i}\cup S_i)\geq \max\{ \theta,\frac{1}{2}(1-\frac{1}{e^2})(\text{OPT}-2\theta)+\theta\}$$ then we can write the as follows:

$$\begin{aligned}
 \nonumber
 \mathbb{E}[(1-\frac{1}{k})^\tau]&=\mathbb{E}[(1-\frac{1}{k})^\tau|\tau^{''}>\tau^{'}]p(\tau^{''}>\tau^{'})+\mathbb{E}[(1-\frac{1}{k})^\tau|\tau^{''}<\tau^{'}]p(\tau^{''}<\tau^{'})
 \\&=\mathbb{E}[(1-\frac{1}{k})^{\tau^{'}}|\tau^{''}>\tau^{'}]p(\tau^{''}>\tau^{'})+\mathbb{E}[(1-\frac{1}{k})^{\tau^{''}}|\tau^{''}<\tau^{'}]p(\tau^{''}<\tau^{'})
 \\&=\sum_{r=1}^{k}(1-\frac{1}{k})^r(p(\tau^{'}=r)+p(\tau^{''}=r))
 \\&=\sum_{r=l}^{k}(1-\frac{1}{k})^r({r-1 \choose l-1}(\frac{k-l}{k})^
{r-l}(\frac{l}{k})^{l}\nonumber\\&\quad+\sum_{r=k-l}^{k}{r-1 \choose k-l-1}(\frac{l}{k})^
{r-k+l}(\frac{k-l}{k})^{k-l})\\&\leq\sum_{r=l}^{k}\exp(\frac{-r}{k}){r-1 \choose l-1}(\frac{k-l}{k})^
{r-l}(\frac{l}{k})^{l}\nonumber\\&\quad+\sum_{r=k-l}^{k}\exp(\frac{-r}{k}){r-1 \choose k-l-1}(\frac{l}{k})^
{r-k+l}(\frac{k-l}{k})^{k-l}\end{aligned}$$

Then using moment generating function(MGF) of negative binomial(NB) distribution we have :

$$\begin{aligned}
    \sum_{r=l}^{k}\exp(\frac{-r}{k}){r-1 \choose l-1}(\frac{k-l}{k})^
{r-l}(\frac{l}{k})^{l}&=\left(\frac{1-\frac{l}{k}}{1-\frac{l}{k}\exp({-\frac{1}{k}})}\right)^l \exp(-\frac{l}{k})\nonumber\\&- \sum_{r=k+1}^{\infty}\exp(\frac{-r}{k}){r-1 \choose l-1}(\frac{k-l}{k})^
{r-l}(\frac{l}{k})^{l}\nonumber\\&\leq \frac{k-l}{k}\exp\left(-\frac{l^2}{k}(1-\exp(-\frac{1}{k}))\right)\nonumber\\&\quad-\exp({-{I_{\frac{l}{k}}}(k+1-l,l+1)})
\\&\leq \frac{k-l}{k}\exp\left(\frac{l^2}{k}((\exp(-1)-1)\frac{1}{k})\right)\nonumber\\&\quad-\exp({-{I_{\frac{l}{k}}}(k+1-l,l+1)})\end{aligned}$$

where the first equality comes from definition of MGF and the first inequality comes from Jensen inequality and definition of CDF of NB distribution and $I_x$ is regularized incomplete beta function. The second inequality comes from the fact that $-1+\exp(-1/k)\leq (\exp(-1)-1)1/k$.\
similarly:

$$\begin{aligned}
    \sum_{r=k-l}^{k}\exp(\frac{-r}{k}){r-1 \choose k-l-1}&(\frac{l}{k})^
{r-k+l}(\frac{k-l}{k})^{k-l}=\left(\frac{1-\frac{k-l}{k}}{1-\frac{k-l}{k}\exp({-\frac{1}{k}})}\right)^{k-l} \exp(-\frac{k-l}{k})\nonumber
\\&- \sum_{r=k+1}^{\infty}\exp(\frac{-r}{k}){r-1 \choose k-l-1}(\frac{l}{k})^
{r-k+l}(\frac{k-l}{k})^{k-l}\nonumber\\&\leq \frac{l}{k}\exp\left(\frac{(k-l)^2}{k}(1-\exp(-\frac{1}{k}))\right)
\\&-\exp({-{I_{\frac{k-l}{k}}}(l+1,k+1-l)})
\\&\leq \frac{l}{k}\exp\left(\frac{(k-l)^2}{k}((\exp(-1)-1)\frac{1}{k})\right)-\exp({-{I_{\frac{k-l}{k}}}(l+1,k+1-l)})\end{aligned}$$

summing up we can write: $$\begin{aligned}
    \mathbb{E}[(1-\frac{1}{k})^\tau]&\leq\frac{l}{k}\exp\left((\frac{k-l}{k})^2((\exp(-1)-1))\right)\notag\\&+(\frac{k-l}{k})\exp\left((\frac{l}{k})^2((\exp(-1)-1)\right)\notag\\&-\exp({-{I_{\frac{k-l}{k}}}(l+1,k+1-l)})\notag\\&-\exp({-{I_{\frac{l}{k}}}(k+1-l,l+1)})\leq \exp\left(((\exp(-1)-1))(1-c)^2\right).\end{aligned}$$ where c is $\max\{k-l/k,l/k\}$.

[^1]: Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, USA. {aadibi@seas.upenn.edu}.

[^2]: Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX, USA. {mokhtari@austin.utexas.edu}.

[^3]: Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, USA.{hassani@seas.upenn.edu}.
