Streaming k-Submodular Maximization under Noise subject to Size Constraint

Lan Nguyen, My T. ThaiICML 2020 · OpenReview

Introduction

Maximizing $k$-submodular functions subject to size constraints is a critical challenge in many real-world optimization tasks, such as maximizing influence across multiple social media topics or placing different types of sensors to maximize information gain. This paper introduces the first streaming algorithms designed to tackle this problem under the realistic constraints of noisy evaluations and massive data scales. The proposed algorithms, DSTREAM and RSTREAM, provide strong theoretical guarantees and achieve solution quality comparable to state-of-the-art non-streaming methods while requiring significantly fewer queries.

The Challenge

Two major hurdles often make $k$-submodular maximization intractable in practice:

  1. Massive Data Scale: Modern datasets are frequently too large to fit in memory. This necessitates algorithms that can process elements in a single pass (a streaming setting).
  2. Noisy Evaluations: Calculating the exact value of an objective function (like expected influence in a network) is often #P-hard. In reality, systems only have access to noisy estimates of these values.

Existing literature has largely ignored the combination of these two challenges. Standard submodular functions have a "pairwise monotonicity" property that does not hold for $k$-submodular functions. This means existing streaming tricks for standard submodularity cannot be directly applied, requiring entirely new mathematical frameworks to handle multiplicative noise robustly.

Proposed Methods

The authors propose two novel streaming algorithms that require only a single scan over the dataset:

  • DSTREAM (Deterministic STREAM): A greedy-style algorithm that adds an element to the solution if its estimated marginal gain is sufficiently large compared to a dynamic threshold. This threshold is updated using a lazy estimation technique to approximate the unknown optimal solution value.
  • RSTREAM (Randomized STREAM): A randomized variant that selects elements with a probability proportional to their estimated gains. Its standout feature is a denoise step. In a streaming setting, noise acts as a "budget killer"—an algorithm might be misled by a noisy spike, pick a low-value element, and waste its limited budget early on. RSTREAM runs multiple "hypotheses" of noise levels to filter out insignificant contributions and prevent premature budget exhaustion.

Experimental Results

The algorithms were evaluated on real-world applications, including Influence Maximization with $k$ topics (using a Facebook dataset) and Sensor Placement with $k$ types of measures (using an Intel Lab dataset).

Competitive Quality, Lower Cost

In influence maximization experiments, the streaming algorithms proved highly effective. RSTREAM (particularly with a denoising parameter $\eta=2$) matched or even slightly exceeded the performance of the standard non-streaming Greedy algorithm.

Solution quality comparison across different budget sizes.

Massive Query Efficiency

While maintaining high solution quality, the streaming algorithms proved to be far more efficient. For a budget of $B=50$, the traditional Greedy algorithm required roughly 6 times more queries than DSTREAM to reach a similar solution.

Number of queries required across different budget sizes.

Tunable Trade-offs

The algorithms also introduce parameters ($\gamma$ and $M$) that allow users to explicitly trade off solution quality for speed. For example, increasing $\gamma$ can reduce the number of queries by 40% while only sacrificing about 13% in solution quality, giving practitioners fine-grained control over computational costs.

Limitations and Future Work

The theoretical guarantees provided in this paper are specifically tailored for multiplicative noise. While this is common, some applications might involve additive noise, which was not the primary focus here. Additionally, the paper focuses on a simple size (cardinality) constraint. Future research could extend these streaming methods to handle more complex constraints, such as knapsack or matroid constraints, in noisy environments.

Summary updated

Abstract

Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining...
BibTeX
@inproceedings{nguyen2020streaming,
  author = {Lan Nguyen and My T. Thai},
  title = {{Streaming k-Submodular Maximization under Noise subject to Size Constraint}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=30qaxviHjr},
}
Figure