Using Partial Monotonicity in Submodular Maximization

Loay Mualem, Moran Feldman

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


Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning applications. Traditionally, the study of submodular functions was based on binary function properties, but recent works began to consider continuous function properties such as the submodularity ratio and the curvature. The monotonicity property of set functions plays a central role in submodular maximization. Nevertheless, no continuous version of this property has been suggested to date (as far as we know), which is unfortunate since submoduar functions that are almost monotone often arise in machine learning applications. In this work we fill this gap by defining the monotonicity ratio, which is a continuous version of the monotonicity property. We then show that for many standard submodular maximization algorithms one can prove new approximation guarantees that depend on the monotonicity ratio; leading to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming, image summarization and ride-share optimization.

שפה מקוריתאנגלית
כותר פרסום המארחAdvances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
עורכיםS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
מוציא לאורNeural information processing systems foundation
מסת"ב (אלקטרוני)9781713871088
סטטוס פרסוםפורסם - 2022
פורסם באופן חיצוניכן
אירוע36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, ארצות הברית
משך הזמן: 28 נוב׳ 20229 דצמ׳ 2022

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

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


כנס36th Conference on Neural Information Processing Systems, NeurIPS 2022
מדינה/אזורארצות הברית
עירNew Orleans

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

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Using Partial Monotonicity in Submodular Maximization'. יחד הם יוצרים טביעת אצבע ייחודית.

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