A Threshold Greedy Algorithm for Noisy Submodular Maximization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929307937406976 |
|---|---|
| author | Chen, Wenjing Xing, Shuo Crawford, Victoria G. |
| author_facet | Chen, Wenjing Xing, Shuo Crawford, Victoria G. |
| contents | We consider the maximization of a submodular objective function $f:2^U\to\mathbb{R}_{\geq 0}$, where the objective $f$ is not accessed as a value oracle but instead subject to noisy queries. We introduce a versatile adaptive sampling procedure called which determines whether the marginal gain of the function $f$ is approximately above or below an input threshold with high probability in as few noisy samples as possible. Using the sampling procedure as a subroutine, we propose sample efficient algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. The proposed algorithms achieve approximation guarantees arbitrarily close to those of the standard value oracle setting. We further provide an experimental evaluation on real instances of submodular maximization and demonstrate the sample efficiency of our proposed algorithm relative to alternative approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_00155 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Threshold Greedy Algorithm for Noisy Submodular Maximization Chen, Wenjing Xing, Shuo Crawford, Victoria G. Data Structures and Algorithms We consider the maximization of a submodular objective function $f:2^U\to\mathbb{R}_{\geq 0}$, where the objective $f$ is not accessed as a value oracle but instead subject to noisy queries. We introduce a versatile adaptive sampling procedure called which determines whether the marginal gain of the function $f$ is approximately above or below an input threshold with high probability in as few noisy samples as possible. Using the sampling procedure as a subroutine, we propose sample efficient algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. The proposed algorithms achieve approximation guarantees arbitrarily close to those of the standard value oracle setting. We further provide an experimental evaluation on real instances of submodular maximization and demonstrate the sample efficiency of our proposed algorithm relative to alternative approaches. |
| title | A Threshold Greedy Algorithm for Noisy Submodular Maximization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.00155 |