Submodular Maximization beyond Non-negativity: Guarantees, fast algorithms, and applications

Christopher Harshaw, Moran Feldman, Justin Ward, Amin Karbasi

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

תקציר

It is generally believed that submodular functions—and the more general class of 7-weakly submodular functions—may only be optimized under the non-negativity assumption f(S) > 0. In this paper, we show that once the function is expressed as the difference f = g — c, where g is monotone, non-negative, and 7-weakly submodular and c is non-negative modular, then strong approximation guarantees may be obtained. We present an algorithm for maximizing g — c under a fc-cardinality constraint which produces a random feasible set S such that E [g(5)-c(S)≥ (1 - e-e)g(OPT)-c(OPT), whose running time is 0 (2 log2 |), independent of k. We extend these results to the unconstrained setting by describing an algorithm with the same approximation guarantees and faster O(n/c log i/c) runtime. The main techniques underlying our algorithms are two-fold: the use of a surrogate objective which varies the relative importance between g and c throughout the algorithm, and a geometric sweep over possible γ values. Our algorithmic guarantees are complemented by a hardness result showing that no polynomial-time algorithm which accesses g through a value oracle can do better. We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset.

שפה מקוריתאנגלית
כותר פרסום המארח36th International Conference on Machine Learning, ICML 2019
מוציא לאורInternational Machine Learning Society (IMLS)
עמודים4684-4705
מספר עמודים22
מסת"ב (אלקטרוני)9781510886988
סטטוס פרסוםפורסם - 2019
אירוע36th International Conference on Machine Learning, ICML 2019 - Long Beach, ארצות הברית
משך הזמן: 9 יוני 201915 יוני 2019

סדרות פרסומים

שם36th International Conference on Machine Learning, ICML 2019
כרך2019-June

כנס

כנס36th International Conference on Machine Learning, ICML 2019
מדינה/אזורארצות הברית
עירLong Beach
תקופה9/06/1915/06/19

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

Publisher Copyright:
Copyright 2019 by the author(s).

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Submodular Maximization beyond Non-negativity: Guarantees, fast algorithms, and applications'. יחד הם יוצרים טביעת אצבע ייחודית.

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