The IMP game: Learnability, approximability and adversarial learning beyond $Σ^0_1$
This work addresses foundational problems in computational learning theory and adversarial machine learning, providing new theoretical insights into the limits of learnability and approximation for complexity classes, which is incremental but with broad implications for the field.
The paper tackles the problem of learnability, approximability, and adversarial learning in computational complexity by introducing the Iterated Matching Pennies (IMP) game framework, showing that it can learn all of Σ⁰₁ ∪ Π⁰₁ and some supersets, with the pursuer having a winning strategy in adversarial learning for Σ⁰₁ but not Π⁰₁, and that some Π⁰₁ languages cannot be approximated by any Σ⁰₁ language.
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 $Σ^0_1 \cup Π^0_1$ 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, $Σ^0_1$ can be learned adversarially, but $Π^0_1$ not); (3) some languages in $Π^0_1$ cannot be approximated by any language in $Σ^0_1$. We show corresponding results also for $Σ^0_i$ and $Π^0_i$ for arbitrary $i$.