The IMP game: Learnability, approximability and adversarial learning beyond ${\Sigma }_1^0$

Abstract

We introduce a problem set-up we call the Iterated Matching Pennies (IMP) game and show that it is a powerful framework for the study of three problems: adversarial learnability, conventional (i.e., non-adversarial) learnability and approximability. Using it, we are able to derive the following theorems. (1) It is possible to learn by example all of ${\Sigma }_1^0\cup {\Pi }_1^0$ as well as some supersets; (2) in adversarial learning (which we describe as a pursuit-evasion game), the pursuer has a winning strategy (in other words, ${\Sigma }_1^0$ can be learned adversarially, but ${\Pi }_1^0$ not); (3) some languages in ${\Pi }_1^0$ cannot be approximated by any language in ${\Sigma }_1^0$. We show corresponding results also for ${\Sigma }_i^0$ and ${\Pi }_i^0$ for arbitrary $i$.

arXiv comment23 pages