Submodular + Concave

Siddharth Mitra, Moran Feldman, Amin Karbasi

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


It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-concave) continuous submodular functions. In this work, we initiate the study of the maximization of functions of the form F(x) = G(x) + C(x) over a solvable convex body P, where G is a smooth DR-submodular function and C is a smooth concave function. This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if G and C are monotone or not, and non-negative or not) and on the nature of the set P (i.e., whether it is downward closed or not), provide 1−1/e, 1/e, or 1/2 approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.

שפה מקוריתאנגלית
כותר פרסום המארחAdvances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
עורכיםMarc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
מוציא לאורNeural information processing systems foundation
מספר עמודים15
מסת"ב (אלקטרוני)9781713845393
סטטוס פרסוםפורסם - 2021
פורסם באופן חיצוניכן
אירוע35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online
משך הזמן: 6 דצמ׳ 202114 דצמ׳ 2021

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

שםAdvances in Neural Information Processing Systems
ISSN (מודפס)1049-5258


כנס35th Conference on Neural Information Processing Systems, NeurIPS 2021
עירVirtual, Online

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

Publisher Copyright:
© 2021 Neural information processing systems foundation. All rights reserved.

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