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.
The algorithm follows three primary steps:
- Candidate Identification: At each step, the algorithm identifies the top $k$ elements based on their expected marginal gain, where $k$ represents the total budget.
- 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."
- 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.
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