Submodular Meta-Learning

Arman Adibi, Aryan Mokhtari, Hamed Hassani

Introduction

Meta-learning has revolutionized how we train AI to "learn how to learn," but most existing frameworks—like the popular Model-Agnostic Meta-Learning (MAML)—are designed for continuous domains where gradient descent is applicable. However, many real-world problems are inherently discrete. Consider a movie recommender system or a ride-sharing application: the goal is not to optimize a continuous weight, but rather to select a specific subset of items (movies or locations) from a massive catalog.

These problems are often modeled as submodular maximization under a cardinality constraint (e.g., "pick the best 10 items to maximize user satisfaction"). While individual tasks can be solved using greedy algorithms, doing so from scratch for every new user at "test time" is computationally expensive. Conversely, a "one-size-fits-all" approach that simply picks the most popular items across all users lacks personalization. This paper bridges the gap between meta-learning and discrete optimization by introducing Submodular Meta-Learning, a framework designed to find an optimal "initialization set" that provides a head start for fast, personalized adaptation.

Methodology

The authors propose a two-stage framework analogous to continuous meta-learning but tailored for discrete sets.

Illustration of the Submodular Meta-Learning framework, showing training tasks, the learned base set, and adaptation to a new task.

In the training phase, the algorithm analyzes a collection of past tasks to find a base set ($S_{tr}$) of size $l$. In the test phase, when a new task arrives, the system quickly adds $k-l$ task-specific elements to that base set to create a personalized solution of size $k$. Just as MAML finds a weight initialization that is "one gradient step away" from a good solution, Submodular Meta-Learning finds a set that is "a few greedy additions away" from a personalized solution.

The core technical challenge is that while the individual tasks are submodular, the "meta-objective" (the function used to find the best base set) is not submodular. To overcome this barrier, the authors introduce two main algorithmic approaches with strong theoretical guarantees:

  1. Meta-Greedy (Deterministic): This algorithm runs two different greedy strategies—one prioritizing the base set and one prioritizing task-specific sets—and selects the best result. The authors prove this achieves at least a 0.53-approximation of the optimal solution.
  2. Randomized Meta-Greedy: This algorithm flips a coin at each step to decide whether to update the base set or the task-specific sets. This approach achieves a near-optimal $(1 - 1/e)$ guarantee (approximately 0.63), matching the famous bound for standard submodular maximization.

Experiments and Results

The researchers evaluated their framework on two real-world scenarios:

  • Uber Ride-Sharing: Using a dataset of roughly 1 million pickups in Manhattan, they modeled a facility location problem to determine optimal driver locations that maximize customer convenience.
  • MovieLens 1M: Using 1 million movie ratings, they built a recommendation task to select a subset of movies maximizing a weighted satisfaction score across different genres for specific users.
Performance comparison of Meta-Greedy algorithms against baselines on Ride Share and Movie Recommendation tasks.

The results highlight a compelling trade-off between efficiency and performance. In the Uber experiments, the Meta-Greedy approach achieved performance nearly identical to "full optimization" (solving the task from scratch at test time) while requiring significantly less computation. Furthermore, the framework consistently outperformed "Greedy-Train" (a non-personalized baseline that only picks the best global set). This demonstrates that even a small amount of task-specific adaptation ($k-l$ elements) provides a massive jump in utility. The Randomized Meta-Greedy algorithm's performance was also shown to be $(1 - 1/e - o(1))$-optimal, essentially reaching the theoretical ceiling for this class of problems.

Limitations and Future Work

While the paper provides a robust foundation for discrete meta-learning, there are a few areas for future expansion:

  • Training Cost: The training phase requires $O(kmn)$ function evaluations. While this is performed offline and can be parallelized, it remains computationally heavy for extremely large-scale task sets.
  • Monotonicity Assumption: The current proofs rely on the functions being monotone (adding more items never decreases value). Extending this to non-monotone submodular functions would open the door to more complex subset selection problems involving diversity or cost penalties.
  • Constraint Variety: The current work focuses on cardinality constraints (fixed set size). Future research could explore more complex constraints, such as matroid or knapsack constraints, broadening the framework's applicability.

Summary updated

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 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.
BibTeX
@inproceedings{adibi2020submodular,
  author = {Arman Adibi and Aryan Mokhtari and Hamed Hassani},
  title = {{Submodular Meta-Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=MribNGgs8LL},
}
Figure