Distributionally robust submodular maximization
Submodular functions have applications throughout machine learning, but in many settings, we do not have direct access to the underlying function f. We focus on stochastic functions that are given as an expectation of functions over a distribution P. In practice, we often have only a limited set of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
MLResearchPress
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129983 |
| _version_ | 1826218034140807168 |
|---|---|
| author | Staib, Matthew Wilder, B Jegelka, Stefanie Sabrina |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Staib, Matthew Wilder, B Jegelka, Stefanie Sabrina |
| author_sort | Staib, Matthew |
| collection | MIT |
| description | Submodular functions have applications throughout machine learning, but in many settings, we do not have direct access to the underlying function f. We focus on stochastic functions that are given as an expectation of functions over a distribution P. In practice, we often have only a limited set of samples fi from P. The standard approach indirectly optimizes f by maximizing the sum of fi. However, this ignores generalization to the true (unknown) distribution. In this paper, we achieve better performance on the actual underlying function f by directly optimizing a combination of bias and variance. Algorithmically, we accomplish this by showing how to carry out distributionally robust optimization (DRO) for submodular functions, providing efficient algorithms backed by theoretical guarantees which leverage several novel contributions to the general theory of DRO. We also show compelling empirical evidence that DRO improves generalization to the unknown stochastic submodular function. |
| first_indexed | 2024-09-23T17:13:07Z |
| format | Article |
| id | mit-1721.1/129983 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:13:07Z |
| publishDate | 2021 |
| publisher | MLResearchPress |
| record_format | dspace |
| spelling | mit-1721.1/1299832022-10-03T11:12:21Z Distributionally robust submodular maximization Staib, Matthew Wilder, B Jegelka, Stefanie Sabrina Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Submodular functions have applications throughout machine learning, but in many settings, we do not have direct access to the underlying function f. We focus on stochastic functions that are given as an expectation of functions over a distribution P. In practice, we often have only a limited set of samples fi from P. The standard approach indirectly optimizes f by maximizing the sum of fi. However, this ignores generalization to the true (unknown) distribution. In this paper, we achieve better performance on the actual underlying function f by directly optimizing a combination of bias and variance. Algorithmically, we accomplish this by showing how to carry out distributionally robust optimization (DRO) for submodular functions, providing efficient algorithms backed by theoretical guarantees which leverage several novel contributions to the general theory of DRO. We also show compelling empirical evidence that DRO improves generalization to the unknown stochastic submodular function. 2021-02-23T22:04:16Z 2021-02-23T22:04:16Z 2019-04 2020-12-21T19:49:32Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/129983 Staib, Matthew et al. "Distributionally robust submodular maximization." 22nd International Conference on Artificial Intelligence and Statistics, April 2019, Naha, Okinawa, Japan, MLResearchPress, April 2019. © 2019 by the author(s) en http://proceedings.mlr.press/v89/staib19a.html 22nd International Conference on Artificial Intelligence and Statistics Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf MLResearchPress arXiv |
| spellingShingle | Staib, Matthew Wilder, B Jegelka, Stefanie Sabrina Distributionally robust submodular maximization |
| title | Distributionally robust submodular maximization |
| title_full | Distributionally robust submodular maximization |
| title_fullStr | Distributionally robust submodular maximization |
| title_full_unstemmed | Distributionally robust submodular maximization |
| title_short | Distributionally robust submodular maximization |
| title_sort | distributionally robust submodular maximization |
| url | https://hdl.handle.net/1721.1/129983 |
| work_keys_str_mv | AT staibmatthew distributionallyrobustsubmodularmaximization AT wilderb distributionallyrobustsubmodularmaximization AT jegelkastefaniesabrina distributionallyrobustsubmodularmaximization |