Resilient Monotone Submodular Function Maximization

  • Authors:
    Vasileios Tzoumas (Univ. of Pennsylvania), Konstantinos Gatsis (Univ. of Pennsylvania), Ali Jadbabie (MIT), George Pappas (Univ. of Pennsylvania)
    Publication ID:
    P090570
    Publication Type:
    Paper
    Received Date:
    22-Mar-2017
    Last Edit Date:
    23-Mar-2017
    Research:
    2386.004 (University of California/Berkeley)

Abstract

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, curvature-dependent 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 analysis with supporting empirical evaluations.

4819 Emperor Blvd, Suite 300 Durham, NC 27703 Voice: (919) 941-9400 Fax: (919) 941-9450

Important Information for the SRC website. This site uses cookies to store information on your computer. By continuing to use our site, you consent to our cookies. If you are not happy with the use of these cookies, please review our Cookie Policy to learn how they can be disabled. By disabling cookies, some features of the site will not work.