Non-Monotone Adaptive Submodular Maximization

Alkis Gotovos, Amin Karbasi, Andreas Krause

Non-Monotone Adaptive Submodular Maximization

Abstract: This paper presents the first algorithm with provable performance guarantees for non-monotone adaptive submodular maximization. By employing a randomized selection strategy from a pool of top candidates, the proposed "Adaptive Random Greedy" policy achieves a $1/e$ approximation ratio. This approach addresses real-world optimization problems where the objective function may decrease as more items are selected, such as sensor placement with costs or viral marketing under complex influence models.

Introduction

In many artificial intelligence applications—including sensor placement, node selection for viral marketing, and active learning—decisions are made sequentially based on observed feedback. This framework is known as adaptive optimization. Traditionally, solutions have relied on the assumption that the objective function is both monotone (adding items never decreases utility) and submodular (exhibiting diminishing returns). However, many practical objectives are non-monotone; for instance, the utility of adding a sensor may eventually be outweighed by its operational cost.

Until this work, no policies provided provable guarantees for these non-monotone, adaptive scenarios. Standard greedy algorithms often fail by selecting items that offer immediate high gains but lead to suboptimal outcomes in the long run.

Methodology: The Adaptive Random Greedy Policy

The authors introduce the Adaptive Random Greedy policy to navigate non-monotone landscapes. Unlike standard greedy approaches that always pick the single best element, this policy introduces randomization to avoid local optima.

Conceptual illustration of the adaptive selection process where items are chosen and states are realized.

The algorithm follows three primary steps:

  1. Candidate Identification: At each step, the algorithm identifies the top $k$ elements based on their expected marginal gain, where $k$ represents the total budget.
  2. Randomized Selection: One of these $k$ elements is selected uniformly at random. This randomization acts as a safety net, preventing the policy from being overly "short-sighted" and committing to a path that might lead to a "trap."
  3. Handling Negative Gains: To account for scenarios where all available choices might decrease total utility, the algorithm includes "dummy" elements with zero marginal gain. This ensures the policy is never forced into a detrimental move.

Theoretically, this approach guarantees a $1/e \approx 0.36$ approximation ratio for non-monotone functions, while retaining the standard $(1 - 1/e) \approx 0.63$ ratio for monotone functions.

Experimental Evaluation

The researchers evaluated the policy using three social network datasets from the KONECT database: Facebook, Google+, and Twitter ego-networks. Each network was subsampled to approximately 2,000 nodes to facilitate computationally intensive Monte Carlo simulations. The primary tasks tested were Influence Maximization (IM), typically monotone, and Maximum Cut (MC), which is non-monotone.

Results and Discussion

The empirical results demonstrate that the Adaptive Random Greedy policy consistently outperforms non-adaptive baselines, particularly in non-monotone tasks.

Performance comparison across Facebook, Google+, and Twitter datasets for Influence Maximization (IM) and Maximum Cut (MC) tasks.

Key findings include:

  • Efficiency in Non-Monotone Tasks: In Maximum Cut experiments on the Facebook dataset, the adaptive policy reached a target utility of 1,900 using only 13 nodes, compared to nearly 30 nodes required by the non-adaptive version.
  • Adaptivity Advantage: The benefit of adaptivity—using feedback to inform subsequent choices—is significantly more pronounced in non-monotone tasks like Max Cut. In these scenarios, knowing which nodes have already been influenced drastically alters the marginal value of future selections.
  • Robustness: The algorithm maintained consistent performance across different network topologies, confirming that the theoretical $1/e$ floor translates to practical reliability. Furthermore, the randomized approach remained competitive even on monotone problems, showing minimal performance loss compared to standard greedy methods.

Conclusion

This work provides a robust theoretical and empirical foundation for non-monotone adaptive submodular maximization. While the calculation of expected marginal gains can be computationally expensive, the Adaptive Random Greedy policy offers a vital tool for complex optimization problems where "more" is not always "better." Future work may focus on optimizing the computational efficiency for massive datasets and exploring stopping criteria that allow the algorithm to terminate early when marginal gains become negligible.

Summary updated

Abstract

A wide range of AI problems, such as sensor placement, active learning, and network influence maximization, require sequentially selecting elements from a large set with the goal of optimizing the utility of the selected subset. Moreover, each element that is picked may provide stochastic feedback, which can be used to make smarter decisions about future selections. Finding efficient policies for this general class of adaptive optimization problems can be extremely hard. However, when the objective function is adaptive monotone and adaptive submodular, a simple greedy policy attains a 1 - 1/e approximation ratio in terms of expected utility. Unfortunately, many practical objective functions are naturally non-monotone; to our knowledge, no existing policy has provable performance guarantees when the assumption of adaptive monotonicity is lifted. We propose the adaptive random greedy policy for maximizing adaptive submodular functions, and prove that it retains the aforementioned 1 - 1/e approximation ratio for functions that are also adaptive monotone, while it additionally provides a 1/e approximation ratio for nonmonotone adaptive submodular functions. We showcase the benefits of adaptivity on three real-world network data sets using two non-monotone functions, representative of two classes of commonly encountered non-monotone objectives.
BibTeX
@inproceedings{gotovos2015non,
  author = {Alkis Gotovos and Amin Karbasi and Andreas Krause},
  title = {{Non-Monotone Adaptive Submodular Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure