Submodular Meta-Learning
  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.
