A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

2016-06-27 · Alina Ene, Huy L. Nguyen

A function $f: \mathbb{Z}_+^E \rightarrow \mathbb{R}_+$ is DR-submodular if it satisfies $f({\bf x} + \chi_i) -f ({\bf x}) \ge f({\bf y} + \chi_i) - f({\bf y})$ for all ${\bf x}\le {\bf y}, i\in E$. Recently, the problem of maximizing a DR-submodular function $f: \mathbb{Z}_+^E \rightarrow \mathbb{R}_+$ subject to a budget constraint $\|{\bf x}\|_1 \leq B$ as well as additional constraints has received significant attention \cite{SKIK14,SY15,MYK15,SY16}. In this note, we give a generic reduction from the DR-submodular setting to the submodular setting. The running time of the reduction and the size of the resulting submodular instance depends only \emph{logarithmically} on $B$. Using this reduction, one can translate the results for unconstrained and constrained submodular maximization to the DR-submodular setting for many types of constraints in a unified manner.

📄 PDF Abstract BibTeX arXiv:1606.08362

Code (0)

등록된 구현이 없습니다.

A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice

2015-12-01 · NeurIPS 2015 12 · Tasuku Soma, Yuichi Yoshida

We consider a generalization of the submodular cover problem based on the concept of diminishing return property on the integer lattice. We are motivated by real scenarios in machine learning that cannot be captured by (…

Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice

2021-11-19 · Alberto Schiabel, Vyacheslav Kungurtsev, Jakub Marecek

Optimization problems with set submodular objective functions have many real-world applications. In discrete scenarios, where the same item can be selected more than once, the domain is generalized from a 2-element set t…

Maximizing Non-Monotone DR-Submodular Functions with Cardinality Constraints

2016-11-29 · Ali Khodabakhsh, Evdokia Nikolova

We consider the problem of maximizing a non-monotone DR-submodular function subject to a cardinality constraint. Diminishing returns (DR) submodularity is a generalization of the diminishing returns property for function…

BIG-bench Machine Learning Combinatorial Optimization

Data Summarization at Scale: A Two-Stage Submodular Approach

2018-06-07 · ICML 2018 7 · Marko Mitrovic, Ehsan Kazemi, Morteza Zadimoghaddam, Amin Karbasi

The sheer scale of modern datasets has resulted in a dire need for summarization techniques that identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuit…

Data Summarization Vocal Bursts Valence Prediction

$γ$-weakly $θ$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions

2026-02-13 · Mohammad Pedramfar, Vaneet Aggarwal arxiv

Optimizing non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study $γ$-weakly $θ$-up-concavity, a novel first-order condition that characterizes a br…