Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910002589990912 |
|---|---|
| author | Liu, Boyu Qin, Lianke Song, Zhao Wang, Yitan Zhao, Jiale |
| author_facet | Liu, Boyu Qin, Lianke Song, Zhao Wang, Yitan Zhao, Jiale |
| contents | Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility is often limit by the $O(knd^2)$ computational bottleneck. In this paper, we propose an integrated framework that addresses efficiency and privacy simultaneously. First, we introduce a novel matrix-based computation paradigm that accelerates function evaluations. Second, we develop approximate data structures that further streamline the optimization process, achieving a theoretical complexity of $O(ε^{-2}(nd+kn+kd^2)\log(k/δ))$. Third, we integrate ($ε, δ$)-DP guaranties to address the privacy concerns inherent in sensitive optimization tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_08367 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration Liu, Boyu Qin, Lianke Song, Zhao Wang, Yitan Zhao, Jiale Machine Learning Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility is often limit by the $O(knd^2)$ computational bottleneck. In this paper, we propose an integrated framework that addresses efficiency and privacy simultaneously. First, we introduce a novel matrix-based computation paradigm that accelerates function evaluations. Second, we develop approximate data structures that further streamline the optimization process, achieving a theoretical complexity of $O(ε^{-2}(nd+kn+kd^2)\log(k/δ))$. Third, we integrate ($ε, δ$)-DP guaranties to address the privacy concerns inherent in sensitive optimization tasks. |
| title | Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2305.08367 |