Abstract: In recent years we have witnessed an increase on the development of methods for submodular optimization, which have been motivated by the wide applicability of submodular functions in real-world data-science problems. In this we consider the problem of robust submodular maximization against unexpected deletions, which may occur due to privacy issues or user preferences. Specifically, we consider the minimum number of items an algorithm has to remember, in order to achieve a non-trivial approximation guarantee against adversarial deletion.

First, we propose a single-pass streaming algorithm that yields a (1-2 epsilon)/4p-approximation for maximizing a non-decreasing submodular function under a general p-matroid constraint and requires a coreset of size k + d/epsilon, where k is the maximum size of a feasible solution. Second, we devise an offline algorithm that guarantees stronger approximation ratios with a coreset of size O(d log k / epsilon).

The talk is based on IEEE ICDM 2022 paper.

Bio: Nikolaj Tatti is an assistant professor at the Department of Computer Science, University of Helsinki. He has published over 70 papers on the topics of various data mining topics such as pattern mining, graph mining, and time series analysis. His research interest include statistical modelling, optimisation algorithms, and algorithms optimising statistical models.

Affiliation: University of Helsinki

Place of Seminar:  Kumpula exactum C323 (in person) & Otaniemi, T5 (streaming)