On the power of learning robustly

Abstract

A class of objects is robustly learnable if not only this class itself is learnable but all of its computable transformations do remain learnable as well. In that sense, being learnable robustly seems to be a desirable property in all fields of learning. This paper studies this phenomenon within the paradigm of inductive inference. It is shown that a more complex topological structures of the classes to be learned leads to positive robustness results, whereas an easy topological structure yields negative results. The counter-intuitive fact that even some self-referential classes can be learned robustly is also shown. Further results concerning uniformly robust learning are summarized.