Online Submodular Maximization via Adaptive Thresholds

Zhengchen Yang, Jiping ZhengIJCAI 2024

Introduction

Submodular maximization is a fundamental problem in machine learning, capturing the essence of "diminishing returns" in tasks like representative frame selection for video summarization or sensor placement. In the modern era of big data, these problems often occur in an online streaming setting, where elements arrive sequentially and decisions to keep or discard them must be made immediately.

The specific challenge addressed in this work is online maximization with replacement. Unlike static streaming, this setting allows for swapping a currently held item for a superior new arrival. Previous approaches struggled with a "trilemma": balancing a high competitive ratio, low memory complexity (ideally $O(k)$ rather than $O(n)$), and minimal computational overhead (oracle calls).

Methodology: The ONLINEADAPTIVE Algorithm

The authors propose ONLINEADAPTIVE, an algorithm that leverages a sophisticated adaptive thresholding strategy. Instead of a static acceptance bar, the algorithm dynamically calculates a threshold $\tau$ based on the marginal gains of items currently in the solution set $S$.

When a new element $v_t$ arrives, the algorithm:

  1. Computes the marginal gain of $v_t$ relative to $S$.
  2. Compares this gain against an adaptive threshold $\tau$, which is a weighted sum of the marginal gains of elements already in $S$.
  3. If $v_t$ exceeds the threshold and $|S|=k$, it replaces the element contributing the least value.
  4. Updates parameters to maintain a balance between solution quality and future flexibility.

By recording marginal gains at the time of acceptance, ONLINEADAPTIVE requires only one function evaluation per element, drastically reducing runtime compared to algorithms that re-evaluate the entire set.

Experimental Results

The algorithm was evaluated on several real-world datasets, including ForestCover (kernel prototype selection) and YouTube (video summarization).

Performance comparison of OnlineAdaptive vs. OnlineNonAdaptive across function value, relative performance, and runtime on ForestCover and YouTube datasets.

As shown in the figure above, ONLINEADAPTIVE consistently achieves high function values and stable relative performance while maintaining efficient runtimes. Key findings include:

  • Theoretical Guarantees: A competitive ratio of at least $1/4$, approaching 0.3178 as the selection size $k$ increases.
  • Efficiency: ONLINEADAPTIVE is orders of magnitude faster than previous state-of-the-art methods like FREEDISPOSAL, which often failed to complete on large datasets due to $O(n)$ memory requirements.
  • Scalability: The $O(k)$ memory footprint ensures the algorithm remains viable for truly massive data streams where $n \gg k$.

Conclusion

ONLINEADAPTIVE sets a new standard for online submodular maximization by effectively solving the efficiency-quality trade-off. By combining adaptive thresholds with replacement, it achieves near-optimal performance with minimal memory and computational cost. Future work may extend this framework to non-monotone or weakly submodular functions.

Summary updated

BibTeX
@inproceedings{yang2024online,
  author = {Zhengchen Yang and Jiping Zheng},
  title = {{Online Submodular Maximization via Adaptive Thresholds}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure