There will be a seminar on Thursday 6 February at 14:30 at LIX, room Grace Hopper with a talk given by Nguyễn Kim Thắng (IBISC).

Title: Online Non-monotone Submodular Maximization: Approximation and Regret Guarantees

Abstract: Submodular and diminishing-returns (DR) submodular optimization are important optimization problems with many real-world applications in machine learning, economics and communication systems. Moreover, DR-submodular optimization captures a subclass of non-convex optimization that provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for the fundamental problems of maximizing non-monotone submodular and DR-submodular functions over convex sets in the online environment. In several settings, these guarantees match the currently best-known ones in the offline environment.