TL;DR
This paper introduces the Stochastic-Lazier-Greedy Algorithm (SLG), a novel approach for maximizing set functions under cardinality constraints, particularly when these functions are non-submodular and data is large-scale or noisy. SLG offers a performance guarantee related to a "submodularity ratio" and generalizes several existing greedy algorithms, providing a more efficient solution than prior methods.
What Problem Does This Paper Address?
Many real-world applications, such as sensor placement, influence maximization, and sparse regression, involve finding the best subset of items (a set function) that maximizes a certain utility, subject to a limit on the number of items chosen (cardinality constraint). While algorithms exist for "monotone submodular" functions, many practical scenarios involve functions that are not submodular. These non-submodular functions, often arising from large-scale or noisy datasets, pose a significant challenge. Existing greedy algorithms for submodular maximization don't directly apply or offer weaker guarantees for these more complex cases. This paper aims to bridge this gap by developing an efficient algorithm for monotone non-submodular maximization that still provides a theoretical performance guarantee.
Methods
The core contribution is the Stochastic-Lazier-Greedy Algorithm (SLG). It's a stochastic variant of the "Lazier-Greedy" algorithm, designed to handle large-scale and noisy data more effectively. Here's how it works:
- Initialization: Start with an empty set
S. - Iteration: In each step, until
Sreaches the desired cardinalityk: - Sample a random value
ξfrom a given distributionD. - Randomly sample a subset
Rof elements from the remaining available elements (V \ S). - Select an element
vfromRthat provides a marginal contribution toSthat is at leastξtimes the maximum possible marginal contribution fromR. - Add
vtoS.
The SLG's efficiency comes from its ability to select elements that are "good enough" (at least ξ-approximation of the best) rather than strictly the best, and by sampling from a subset R rather than the entire remaining set. This approach reduces the number of function evaluations needed compared to simpler greedy methods. The paper also introduces the concept of a "submodularity ratio" (γs,k(f)) to quantify how close a function is to being submodular, which is crucial for analyzing the algorithm's performance guarantee.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Bridging the Gap: The paper successfully extends the benefits of greedy algorithms (efficiency, theoretical guarantees) to the more challenging domain of non-submodular set functions, which are more prevalent in real-world applications.
- Submodularity Ratio as a Measure: The introduction and use of the
γs,k(f)ratio is a key theoretical contribution. It provides a principled way to measure how "submodular-like" a function is, and this measure directly influences the algorithm's performance guarantee. A function closer to submodular (higher ratio) leads to a better guarantee. - Efficiency Through Stochasticity and Laziness: The SLG cleverly combines randomness (
ξsampling) with a "lazier" selection criterion (not necessarily the absolute best marginal gain) and sampling from a subsetR. This allows it to achieve a performance guarantee with significantly fewer function evaluations than previous methods like the Stochastic-Standard-Greedy algorithm. - Unified Framework: The SLG is presented as a generalization of several well-known greedy algorithms (Standard-Greedy, Lazier-Greedy, Stochastic-Standard-Greedy), demonstrating its broad applicability and theoretical significance.
Key Results
The main result is the performance guarantee for the SLG algorithm in expectation for monotone non-submodular maximization. The algorithm achieves an approximation guarantee of (1 - e^(-μ/min) - ε), where:
μis the expected value of the sampled random variableξ.minis a parameter derived from the submodularity ratio, representing the worst-case submodularity of the function.εis a small error term related to the sampling process.
Crucially, the number of function evaluations required by SLG is O(n log(1/ε)), which is linear in the size of the ground set n and independent of the cardinality k. This is a significant improvement over algorithms like the Stochastic-Standard-Greedy algorithm, which require O(nk) evaluations.
Limitations and Future Work
- Theoretical Focus: The paper is primarily theoretical, focusing on algorithm design and performance guarantees. Empirical validation on real-world datasets would be a valuable next step to demonstrate practical performance.
- Submodularity Ratio Estimation: While the submodularity ratio is central to the guarantee, estimating it in practice for arbitrary non-submodular functions might be challenging.
- Choice of Parameters: The performance guarantee depends on the choice of the distribution
Dand the subset sizes. Further research could explore optimal strategies for selecting these parameters in different scenarios. - Monotonicity Assumption: The algorithm and its guarantee are based on the assumption that the set function is monotone. Extending this to non-monotone functions would be a significant advancement.
Summary updated