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
المدة: ٦ ديسمبر ٢٠٢١١٤ ديسمبر ٢٠٢١

سلسلة المنشورات

الاسمAdvances in Neural Information Processing Systems
مستوى الصوت14
رقم المعيار الدولي للدوريات (المطبوع)1049-5258


!!Conference35th Conference on Neural Information Processing Systems, NeurIPS 2021
المدينةVirtual, Online

ملاحظة ببليوغرافية

Funding Information:
Funding in direct support of this work: The work of Moran Feldman was supported in part by Israel Science Foundation (ISF) grant no. 459/20. Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS-1845032) and ONR (N00014-19-1-2406).

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

قم بذكر هذا