Regularized Unconstrained Weakly Submodular Maximization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917751785783296 |
|---|---|
| author | Zhu, Yanhui Basu, Samik Pavan, A. |
| author_facet | Zhu, Yanhui Basu, Samik Pavan, A. |
| contents | Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(\frac{n}ε\log \frac{n}{γε})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq γ(1-ε)f(OPT)-c(OPT)-\frac{c(OPT)}{γ(1-ε)}\log\frac{f(OPT)}{c(OPT)}$, where $γ$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04620 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Regularized Unconstrained Weakly Submodular Maximization Zhu, Yanhui Basu, Samik Pavan, A. Data Structures and Algorithms Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(\frac{n}ε\log \frac{n}{γε})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq γ(1-ε)f(OPT)-c(OPT)-\frac{c(OPT)}{γ(1-ε)}\log\frac{f(OPT)}{c(OPT)}$, where $γ$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions. |
| title | Regularized Unconstrained Weakly Submodular Maximization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.04620 |