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 