A Unified Approach for Maximizing Continuous DR-submodular Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929207301373952 |
|---|---|
| author | Pedramfar, Mohammad Quinn, Christopher John Aggarwal, Vaneet |
| author_facet | Pedramfar, Mohammad Quinn, Christopher John Aggarwal, Vaneet |
| contents | This paper presents a unified approach for maximizing continuous DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function or only the function value, and where the oracle access is either deterministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives new/improved results for nine out of the sixteen considered cases, avoids computationally expensive projections in two cases, with the proposed framework matching performance of state-of-the-art approaches in the remaining five cases. Notably, our approach for the stochastic function value-based oracle enables the first regret bounds with bandit feedback for stochastic DR-submodular functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_16671 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Unified Approach for Maximizing Continuous DR-submodular Functions Pedramfar, Mohammad Quinn, Christopher John Aggarwal, Vaneet Machine Learning Artificial Intelligence Computational Complexity This paper presents a unified approach for maximizing continuous DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function or only the function value, and where the oracle access is either deterministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives new/improved results for nine out of the sixteen considered cases, avoids computationally expensive projections in two cases, with the proposed framework matching performance of state-of-the-art approaches in the remaining five cases. Notably, our approach for the stochastic function value-based oracle enables the first regret bounds with bandit feedback for stochastic DR-submodular functions. |
| title | A Unified Approach for Maximizing Continuous DR-submodular Functions |
| topic | Machine Learning Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2305.16671 |