Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization

Alan Kuhnle

TL;DR

This paper introduces "Simultaneous Sieves," a deterministic, single-pass streaming algorithm for a challenging optimization problem: finding the best subset of items (up to a certain size) that maximizes a "diminishing returns" function, even when that function doesn't strictly increase. This new algorithm significantly improves upon previous deterministic methods, achieving approximation ratios close to the theoretical best, even matching the performance of randomized approaches.

What Problem Does This Paper Address?

Many real-world problems involve selecting a subset of items to maximize some objective, subject to a limit on the number of items chosen. Think of viral marketing (selecting users to spread a message), network monitoring (choosing sensors), or video summarization (picking clips). These problems often exhibit "submodularity," meaning the value of adding a new item decreases as you already have more items. This is the "diminishing returns" property. The specific challenge here is Submodular Maximization with a Cardinality Constraint (SMCC), especially when the submodular function is non-monotone. Non-monotone means that adding an item might decrease the total value, which makes the problem much harder.

Furthermore, in many applications, the data arrives sequentially (a "stream"), and we can't store everything. We need streaming algorithms that process data in a single pass, using limited memory. For monotone functions, near-optimal streaming algorithms exist. However, for non-monotone functions, the best deterministic streaming algorithms lag behind randomized ones. This paper aims to bridge that gap by providing a deterministic streaming algorithm that achieves strong approximation guarantees for non-monotone SMCC.

Methods

The core of the proposed algorithm, "Simultaneous Sieves," is a clever generalization of a known technique for monotone functions. Instead of running just one greedy selection process, it runs $l$ independent "single-threshold greedy" algorithms simultaneously. Each of these $l$ algorithms tries to build a solution by adding elements that provide the highest marginal gain, as long as that gain exceeds a certain threshold related to the optimal solution. These $l$ algorithms compete for incoming elements, with each element being assigned to the algorithm that can gain the most from it.

After the stream has been processed, a post-processing step is applied. This step takes the union of the $l$ solutions generated by the greedy algorithms and then uses an existing offline (non-streaming) $\alpha$-approximation algorithm for SMCC to refine this combined set. The choice of $l$ (the number of simultaneous greedy algorithms) is set to $1/\varepsilon$, where $\varepsilon$ is a parameter controlling the approximation error.

For the case where the function is monotone, the algorithm simplifies to the optimal streaming algorithm by setting $l=1$ and using an optimal post-processing step.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Deterministic Power for Non-Monotone Functions: The most significant insight is demonstrating that strong, deterministic approximation guarantees are achievable for non-monotone SMCC in a streaming setting, closing the gap with randomized approaches.
  • Simultaneous Greedy Competition: Running multiple greedy algorithms in parallel and letting them compete for elements is a powerful strategy. It allows the algorithm to explore different potential solution paths simultaneously, which is crucial for non-monotone functions where a locally optimal choice might not lead to a globally good solution.
  • Leveraging Offline Approximations: The algorithm cleverly uses an existing offline approximation algorithm as a black box for post-processing. This modularity allows it to inherit the approximation guarantees of the offline component.
  • Near-Optimal Deterministic Performance: The algorithm achieves an approximation ratio of $\alpha/(1+\alpha) - \varepsilon$, which is remarkably close to the theoretical optimum of $1/2$ for non-monotone SMCC, especially when an exponential-time offline algorithm is used for post-processing.

Key Results

  • The paper presents a deterministic, single-pass streaming algorithm for non-monotone SMCC.
  • It achieves an approximation ratio of $\alpha/(1+\alpha) - \varepsilon$, where $\alpha$ is the ratio of the offline post-processing algorithm.
  • When an optimal offline algorithm is used (exponential time), the algorithm deterministically achieves nearly the optimal $1/2$ ratio.
  • Using a known deterministic $1/e$-approximation offline algorithm, the algorithm achieves a ratio of approximately $0.2689$. This is a significant improvement over the previous best deterministic single-pass ratio of $1/9 \approx 0.1111$.
  • The algorithm's performance nearly matches the expected ratio of $0.2779$ achieved by a recent randomized streaming algorithm.
  • For monotone functions, the algorithm reduces to the optimal streaming algorithm of Badanidiyuru et al. (2014).

Limitations and Future Work

  • Dependency on Offline Algorithm: The approximation ratio is dependent on the quality of the offline $\alpha$-approximation algorithm used for post-processing. If a weaker offline algorithm is used, the streaming algorithm's guarantee will also be weaker.
  • Parameter $\varepsilon$: The approximation ratio includes an $\varepsilon$ term, meaning a tighter guarantee requires a larger $l$ (more simultaneous greedy algorithms), potentially increasing computational cost.
  • Theoretical Focus: The paper is primarily theoretical. While it discusses improvements in approximation ratios and complexity, empirical validation on real-world datasets would be a valuable next step.
  • Future Work: The authors suggest exploring further improvements in the approximation ratio and potentially reducing the space or time complexity. Investigating the trade-offs between the number of simultaneous greedy algorithms ($l$) and the resulting approximation guarantee is also a natural direction.

Summary updated

Abstract

In this work, we present a combinatorial, deterministic single-pass streaming algorithm for the problem of maximizing a submodular function, not necessarily monotone, with respect to a cardinality constraint (SMCC). In the case the function is monotone, our algorithm reduces to the optimal streaming algorithm of Badanidiyuru et al. (2014). In general, our algorithm achieves ratio $\alpha / (1 + \alpha) - \varepsilon$, for any $\varepsilon > 0$, where $\alpha$ is the ratio of an offline (deterministic) algorithm for SMCC used for post-processing. Thus, if exponential computation time is allowed, our algorithm deterministically achieves nearly the optimal $1/2$ ratio. These results nearly match those of a recently proposed, randomized streaming algorithm that achieves the same ratios in expectation. For a deterministic, single-pass streaming algorithm, our algorithm achieves in polynomial time an improvement of the best approximation factor from $1/9$ of previous literature to $\approx 0.2689$.
BibTeX
@misc{kuhnle2020simultaenous,
  author = {Alan Kuhnle},
  title = {{Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization}},
  year = {2020},
  eprint = {2010.14367},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.14367},
}
Figure