Adaptive Submodular Meta-Learning

Shaojie Tang, Jing YuanarXiv 2020 · OpenReview

Abstract

Meta-Learning has gained increasing attention in the machine learning and artificial intelligence communities. In this paper, we introduce and study an adaptive submodular meta-learning problem. The input of our problem is a set of items, where each item has a random state which is initially unknown. The only way to observe an item's state is to select that item. Our objective is to adaptively select a group of items that achieve the best performance over a set of tasks, where each task is represented as an adaptive submodular function that maps sets of items and their states to a real number. To reduce the computational cost while maintaining a personalized solution for each future task, we first select an initial solution set based on previously observed tasks, then adaptively add the remaining items to the initial solution set when a new task arrives. As compared to the solution where a brand new solution is computed for each new task, our meta-learning based approach leads to lower computational overhead at test time since the initial solution set is pre-computed in the training stage. To solve this problem, we propose a two-phase greedy policy and show that it achieves a $1/2$ approximation ratio for the monotone case. For the non-monotone case, we develop a two-phase randomized greedy policy that achieves a $1/32$ approximation ratio.

Introduction

Meta-learning has revolutionized how models adapt to new tasks, particularly in continuous domains through frameworks like Model-Agnostic Meta-Learning (MAML). However, extending these benefits to discrete optimization—specifically subset selection—remains a significant challenge. While recent research has explored discrete meta-learning using submodular optimization, these approaches typically assume a static environment where the properties of items are known upfront.

In many real-world applications, such as active learning or adaptive viral marketing, the environment is stochastic. The true state of an item (e.g., whether a specific user will engage with a piece of content) is hidden until that item is selected. This creates a tension between computational efficiency and personalization: a purely offline solution is fast but fails to adapt to task-specific feedback, while a purely online adaptive solution provides high performance but incurs prohibitive computational costs at test time. This paper introduces the framework of Adaptive Submodular Meta-Learning to bridge this gap.

The Two-Phase Framework

The core of our approach is a two-stage selection process parameterized by a total budget $k$ and an initial offline budget $l$. This structure allows a decision-maker to balance the trade-off between pre-computation and real-time adaptation.

  1. Initialization Phase (Offline/Training): Using historical task data, the algorithm selects a fixed set of $l$ items. This set is task-independent and computed before any specific test task is encountered, meaning it contributes zero computational overhead during the execution phase.
  2. Execution Phase (Online/Testing): Once a new task arrives, the algorithm observes the realized states of the $l$ pre-selected items. It then adaptively selects the remaining $k-l$ items one by one, updating its strategy based on the feedback received from each subsequent selection.

A critical theoretical insight of this work is that the combination of offline and online selection breaks the standard property of "adaptive submodularity." Because the initial $l$ items must be chosen without knowing the specific task, the uncertainty violates the conditions required for traditional adaptive greedy proofs. Consequently, new mathematical techniques were required to establish performance bounds for this hybrid model.

Proposed Algorithms

To address both monotone and non-monotone objective functions, we propose two distinct policies:

Two-phase Greedy Policy (TGP)

For monotone tasks—where adding an item never decreases the total utility—the TGP employs a greedy strategy in both phases. In the offline phase, it selects items that maximize the expected marginal utility across the distribution of training tasks. In the online phase, it selects items that maximize the expected marginal utility relative to the specific task and the observed states of previously selected items.

Two-phase Randomized Greedy Policy

In non-monotone scenarios (e.g., where excessive selection might lead to diminishing returns or negative impacts), standard greedy approaches often fail. We develop a randomized policy that selects items uniformly at random from a candidate pool of the highest-performing items. To prevent the selection of items with negative marginal utility, we incorporate "dummy items" with zero utility into the selection pool, ensuring the algorithm can effectively "stop" or skip a selection if no beneficial items remain.

Theoretical and Empirical Results

Our theoretical analysis proves that these policies provide robust approximation guarantees despite the loss of standard adaptive submodularity:

  • Monotone Case: The TGP achieves a 1/2 approximation ratio.
  • Non-monotone Case: The randomized policy achieves a 1/32 approximation ratio, with tighter bounds (up to $1/2e$) in specific edge cases.

We evaluated these algorithms using the NetHEPT dataset, a collaboration network of 15,233 nodes and 62,774 edges. By simulating influence maximization tasks with varying propagation probabilities, we compared TGP against state-of-the-art non-adaptive baselines (such as Randomized Meta-Greedy) and purely offline training.

The results demonstrate that TGP consistently outperforms non-adaptive methods. Notably, as the total budget $k$ increases, the performance gap between our adaptive meta-learning approach and non-adaptive baselines widens. This suggests that test-time adaptation becomes increasingly critical as the scale of the selection problem grows.

Conclusion

Adaptive Submodular Meta-Learning provides a principled way to handle discrete optimization in uncertain environments. By utilizing the $l$ parameter as a "dial," practitioners can customize the balance between speed and personalization. While current guarantees assume a known prior distribution of item states, future work will focus on automating the selection of the budget split $l$ and extending the framework to settings where the state distributions must be learned entirely from scratch.

Summary updated

Abstract

Meta-Learning has gained increasing attention in the machine learning and artificial intelligence communities. In this paper, we introduce and study an adaptive submodular meta-learning problem. The input of our problem is a set of items, where each item has a random state which is initially unknown. The only way to observe an item's state is to select that item. Our objective is to adaptively select a group of items that achieve the best performance over a set of tasks, where each task is represented as an adaptive submodular function that maps sets of items and their states to a real number. To reduce the computational cost while maintaining a personalized solution for each future task, we first select an initial solution set based on previously observed tasks, then adaptively add the remaining items to the initial solution set when a new task arrives. As compared to the solution where a brand new solution is computed for each new task, our meta-learning based approach leads to lower computational overhead at test time since the initial solution set is pre-computed in the training stage. To solve this problem, we propose a two-phase greedy policy and show that it achieves a $1/2$ approximation ratio for the monotone case. For the non-monotone case, we develop a two-phase randomized greedy policy that achieves a $1/32$ approximation ratio.
BibTeX
@misc{tang2020adaptive,
  author = {Shaojie Tang and Jing Yuan},
  title = {{Adaptive Submodular Meta-Learning}},
  year = {2020},
  eprint = {2012.06070},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.06070},
}
Figure