Abstract
This paper addresses the challenge of stochastic submodular maximization in scenarios where an item's cost is not fixed but depends on its random performance. We introduce the Correlated Stochastic Submodular Maximization Problem (CSSMP) framework and propose an adaptive algorithm combining stochastic continuous greedy optimization with a lattice-based contention resolution scheme. Our approach provides a theoretical performance guarantee of approximately 11% of the optimal policy. Empirical evaluations in recommendation systems and active learning demonstrate that our method achieves superior and more stable performance compared to traditional greedy baselines.
Introduction
Submodular maximization is a fundamental tool for modeling "diminishing returns" in computer science. For instance, in information retrieval, the marginal utility of additional documents decreases as more information is gathered. While existing models often account for uncertainty in item performance, they typically assume item costs are fixed. This paper argues that in many real-world applications, such as recommendation systems and active learning, the cost of an item is intrinsically linked to its realized performance.
Problem Statement
The authors identify a critical gap: the lack of an optimization framework for cases where both performance and cost are random and correlated.
- Recommendation Systems: A long article's "cost" (user time) is high only if the user reads it (high performance). If they skip it, the cost is negligible.
- Active Learning: The time required for an expert to label data (cost) depends on the information density of the batch (performance).
Methodology
The proposed solution for the Correlated Stochastic Submodular Maximization Problem (CSSMP) involves two phases:
1. Continuous Optimization Phase
The discrete problem is relaxed into a continuous version. A Stochastic Continuous Greedy algorithm is employed to find a fractional solution that maximizes expected utility within a "soft" budget constraint.
2. Rounding Phase (Adaptive Policy)
To translate fractional solutions into discrete decisions, the authors extend the Contention Resolution Scheme (CRS) to lattice-submodular functions. This extension allows items to have multiple performance levels rather than binary states. The resulting policy is adaptive: it observes an item's performance and cost in real-time to adjust subsequent selections based on the remaining budget.
Experimental Evaluation
The framework was tested on two primary datasets:
- Synthetic Recommendation Datasets: 18 settings simulating news platforms with varying user preferences.
- WDBC Dataset: The Wisconsin Diagnostic Breast Cancer dataset was used for batch-mode active learning, aiming to select informative data points under a strict time budget.
Key Results and Insights
- Theoretical Robustness: The algorithm guarantees a constant factor approximation ratio of $(1 - 1/\sqrt[4]{e})/2 \approx 0.110$. This ensures the algorithm avoids catastrophic failure regardless of input.
- Superior Performance and Stability: In recommendation simulations, the algorithm outperformed greedy baselines in 14 of 18 settings and showed significantly higher stability across random seeds.
- Active Learning Gains: The method more effectively reduced prediction error in 7 out of 8 experimental settings for the breast cancer diagnostic task.
- Lattice Framework: Moving from sets to lattices allows for a richer description of item states, essential when costs depend on the degree of success.
Conclusion
While the proposed method offers strong theoretical guarantees and empirical performance, its computational complexity remains a challenge. Future work will focus on integrating fast submodular maximization techniques to improve scalability for large-scale production environments.
Summary updated