ΟΜΙΛΙΑ: Resilient Monotone Submodular Maximization

Printer-friendly versionSend by email

ABSTRACT

In this talk, 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 may involve objective functions that are monotone and submodular. In this paper, we provide for the solution of such optimization problems the first scalable approximation algorithm 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 optimization problems, yet its effect on resilient optimization had hitherto been unknown. We complement our theoretical analyses with empirical evaluations

(Full paper is available at https://arxiv.org/pdf/1703.07280v2.pdf)

Speaker Bio:

Vasileios Tzoumas is a PhD candidate at the University of Pennsylvania (UPenn), Department of Electrical and Systems Engineering, and a visiting PhD student at the Massachusetts Institute of Technology (MIT), Institute for Data, Systems, and Society. He holds a diploma (BSc) in Electrical and Computer Engineering from the National Technical University of Athens (NTUA), Greece, a Master of science (MSc) in Electrical Engineering from UPenn, USA, and a master of arts (MA) in Statistics from the Wharton School of Business at UPenn, USA. In December 2017, Vasileios was a Best Student Paper Award finalist in the 56th IEEE Conference in Decision and Control. Vasileios' research interests include the resource-constrained design of large-scale systems with applications in estimation and control; to this end, he uses and develops tools in the theory of submodular function maximization.

Where: 
Αίθουσα Διαλέξεων, Ι.Π.&Τ.
Location: 
ΕΚΕΦΕ "ΔΗΜΟΚΡΙΤΟΣ"

© 2018 - Institute of Informatics and Telecommunications | National Centre for Scientific Research "Demokritos"