Resilient monotone submodular function maximization
In this paper, we focus on applications in machine learning, optimization, and control that call for the resilient selection of a few elements, e.g. features, sensors, or leaders, against a number of adversarial denial-of-service attacks or failures. In general, such resilient optimization problems...
| Auteurs principaux: | , , , |
|---|---|
| Format: | Conference item |
| Langue: | English |
| Publié: |
Institute of Electrical and Electronics Engineers
2017
|
| _version_ | 1826261897386655744 |
|---|---|
| author | Tzoumas, V Gatsis, K Jadbabaie, A Pappas, GJ |
| author_facet | Tzoumas, V Gatsis, K Jadbabaie, A Pappas, GJ |
| author_sort | Tzoumas, V |
| collection | OXFORD |
| description | In this paper, we focus on applications in machine learning, optimization, and control that call for the resilient selection of a few elements, e.g. features, sensors, or leaders, against a number of adversarial denial-of-service attacks or failures. In general, such resilient optimization problems are hard, and cannot be solved exactly in polynomial time, even though they often involve objective functions that are monotone and submodular. Notwithstanding, in this paper we provide the first scalable algorithm for their approximate solution, that is valid for any number of attacks or failures, and which, for functions with low curvature, guarantees superior approximation performance. Notably, the curvature has been known to tighten approximations for several non-resilient maximization problems, yet its effect on resilient maximization had hitherto been unknown. We complement our theoretical analyses with supporting empirical evaluations. |
| first_indexed | 2024-03-06T19:27:48Z |
| format | Conference item |
| id | oxford-uuid:1c61f53d-94fd-447e-a554-986a9af52551 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:27:48Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | oxford-uuid:1c61f53d-94fd-447e-a554-986a9af525512022-03-26T11:05:22ZResilient monotone submodular function maximizationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:1c61f53d-94fd-447e-a554-986a9af52551EnglishSymplectic ElementsInstitute of Electrical and Electronics Engineers2017Tzoumas, VGatsis, KJadbabaie, APappas, GJIn this paper, we focus on applications in machine learning, optimization, and control that call for the resilient selection of a few elements, e.g. features, sensors, or leaders, against a number of adversarial denial-of-service attacks or failures. In general, such resilient optimization problems are hard, and cannot be solved exactly in polynomial time, even though they often involve objective functions that are monotone and submodular. Notwithstanding, in this paper we provide the first scalable algorithm for their approximate solution, that is valid for any number of attacks or failures, and which, for functions with low curvature, guarantees superior approximation performance. Notably, the curvature has been known to tighten approximations for several non-resilient maximization problems, yet its effect on resilient maximization had hitherto been unknown. We complement our theoretical analyses with supporting empirical evaluations. |
| spellingShingle | Tzoumas, V Gatsis, K Jadbabaie, A Pappas, GJ Resilient monotone submodular function maximization |
| title | Resilient monotone submodular function maximization |
| title_full | Resilient monotone submodular function maximization |
| title_fullStr | Resilient monotone submodular function maximization |
| title_full_unstemmed | Resilient monotone submodular function maximization |
| title_short | Resilient monotone submodular function maximization |
| title_sort | resilient monotone submodular function maximization |
| work_keys_str_mv | AT tzoumasv resilientmonotonesubmodularfunctionmaximization AT gatsisk resilientmonotonesubmodularfunctionmaximization AT jadbabaiea resilientmonotonesubmodularfunctionmaximization AT pappasgj resilientmonotonesubmodularfunctionmaximization |