GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
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_ | 1866908603230715904 |
|---|---|
| author | Fahrbach, Matthew Ramalingam, Srikumar Zadimoghaddam, Morteza Ahmadian, Sara Citovsky, Gui DeSalvo, Giulia |
| author_facet | Fahrbach, Matthew Ramalingam, Srikumar Zadimoghaddam, Morteza Ahmadian, Sara Citovsky, Gui DeSalvo, Giulia |
| contents | This work studies a novel subset selection problem called max-min diversification with monotone submodular utility ($\textsf{MDMS}$), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of $\textsf{MDMS}$ is to maximize $f(S) = g(S) + λ\cdot \texttt{div}(S)$ subject to a cardinality constraint $|S| \le k$, where $g(S)$ is a monotone submodular function and $\texttt{div}(S) = \min_{u,v \in S : u \ne v} \text{dist}(u,v)$ is the max-min diversity objective. We propose the $\texttt{GIST}$ algorithm, which gives a $\frac{1}{2}$-approximation guarantee for $\textsf{MDMS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of $0.5584$. Finally, we show in our empirical study that $\texttt{GIST}$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18754 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility Fahrbach, Matthew Ramalingam, Srikumar Zadimoghaddam, Morteza Ahmadian, Sara Citovsky, Gui DeSalvo, Giulia Data Structures and Algorithms Machine Learning This work studies a novel subset selection problem called max-min diversification with monotone submodular utility ($\textsf{MDMS}$), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of $\textsf{MDMS}$ is to maximize $f(S) = g(S) + λ\cdot \texttt{div}(S)$ subject to a cardinality constraint $|S| \le k$, where $g(S)$ is a monotone submodular function and $\texttt{div}(S) = \min_{u,v \in S : u \ne v} \text{dist}(u,v)$ is the max-min diversity objective. We propose the $\texttt{GIST}$ algorithm, which gives a $\frac{1}{2}$-approximation guarantee for $\textsf{MDMS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of $0.5584$. Finally, we show in our empirical study that $\texttt{GIST}$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet. |
| title | GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2405.18754 |