Theory Day Session 3

Yishay Mansour – Robust inference and local algorithms

Robust inference is an extension of probabilistic inference, where some of the observations are adversarially corrupted. We model it as a zero-sum game between the adversary, who can select a modification rule, and the predictor, who wants to accurately predict the state of nature. There are two variants of the model, one where the adversary needs to pick the modification rule in advance and one where the adversary can select the modification rule after observing the realized input. For both settings we derive efficient near optimal policy which runs in polynomial time. Our efficient algorithms are based on methodologies for developing local computation algorithms, and establish an interesting connection between the two areas. Based on joint works with Uriel Feige, Aviad Rubinstein, Robert Schapire, Moshe Tennenholtz, Shai Vardi.