Do less, get more: Streaming submodular maximization with subsampling

Moran Feldman, Amin Karbasi, Ehsan Kazemi

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים


In this paper, we develop the first one-pass streaming algorithm for submodular maximization that does not evaluate the entire stream even once. By carefully subsampling each element of the data stream, our algorithm enjoys the tightest approximation guarantees in various settings while having the smallest memory footprint and requiring the lowest number of function evaluations. More specifically, for a monotone submodular function and a p-matchoid constraint, our randomized algorithm achieves a 4p approximation ratio (in expectation) with O(k) memory and O(km/p) queries per element (k is the size of the largest feasible solution and m is the number of matroids used to define the constraint). For the non-monotone case, our approximation ratio increases only slightly to 4p + 2 o(1). To the best or our knowledge, our algorithm is the first that combines the benefits of streaming and subsampling in a novel way in order to truly scale submodular maximization to massive machine learning problems. To showcase its practicality, we empirically evaluated the performance of our algorithm on a video summarization application and observed that it outperforms the state-of-the-art algorithm by up to fifty-fold while maintaining practically the same utility. We also evaluated the scalability of our algorithm on a large dataset of Uber pick up locations.

שפה מקוריתאנגלית
עמודים (מ-עד)732-742
מספר עמודים11
כתב עתAdvances in Neural Information Processing Systems
סטטוס פרסוםפורסם - 2018
אירוע32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, קנדה
משך הזמן: 2 דצמ׳ 20188 דצמ׳ 2018

הערה ביבליוגרפית

Publisher Copyright:
© 2018 Curran Associates Inc..All rights reserved.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Do less, get more: Streaming submodular maximization with subsampling'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי