Systems | Information | Learning | Optimization

Adversarial influence maximization and Bandits meet Matrix Completion


Speaker 1: Justin Khim
Title: Adversarial influence maximization

Abstract: We consider the problem of influence maximization in fixed networks. The goal is to select a subset of nodes of a specified size to infect so that the number of infected nodes at the conclusion of the epidemic is as large as possible. We introduce an adversarial setting in which an adversary is allowed to specify the edges through which contagion may spread, and the player chooses sets of nodes to infect in successive rounds. We establish upper and lower bounds on the minimax pseudo-regret in both undirected and directed networks.

Speaker 2: Aniruddha Bhargava
Title: Bandits meet Matrix Completion

Abstract: The classical bandit problem assumes a fixed distribution of rewards over a set of arms. There’s been work done before to model multiple populations. Most of them rely on some form of clustering or classification using side information about the users. What if we don’t have side information?
In this work, we propose a new method that reformulates the multi-population bandit modeling as that of completing a symmetric positive semi-definite matrix. The results are in itself new in the area of active matrix completion of SPSD matrices. I will also present some simulation results on data modeled from human feedback.

November 30 @ 12:30
12:30 pm (1h)

Discovery Building, Orchard View Room

Aniruddha Bhargava, Justin Khim