Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization

Lu Han, Min Li, Dachuan Xu, Dongmei ZhangJournal of Industrial and Management Optimization 2020 · DOI

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:

  1. Initialization: Start with an empty set S.
  2. Iteration: In each step, until S reaches the desired cardinality k:
  3. Sample a random value ξ from a given distribution D.
  4. Randomly sample a subset R of elements from the remaining available elements (V \ S).
  5. Select an element v from R that provides a marginal contribution to S that is at least ξ times the maximum possible marginal contribution from R.
  6. Add v to S.

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 subset R. 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 ξ.
  • min is 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 D and the subset size s. 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

Abstract

<p style='text-indent:20px;'>The problem of maximizing a given set function with a cardinality constraint has widespread applications. A number of algorithms have been provided to solve the maximization problem when the set function is monotone and submodular. However, reality-based set functions may not be submodular and may involve large-scale and noisy data sets. In this paper, we present the Stochastic-Lazier-Greedy Algorithm (SLG) to solve the corresponding non-submodular maximization problem and offer a performance guarantee of the algorithm. The guarantee is related to a submodularity ratio, which characterizes the closeness of to submodularity. Our algorithm also can be viewed as an extension of several previous greedy algorithms.
BibTeX
@article{han2020stochastic,
  author = {Lu Han and Min Li and Dachuan Xu and Dongmei Zhang},
  title = {{Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization}},
  journal = {Journal of Industrial and Management Optimization},
  year = {2020},
  doi = {10.3934/jimo.2020085},
}
Figure