Title: On Fundamental Limits of Robust Learning,
Abstract: We consider the problems of robust PAC learning from distributed and
streaming data, which may contain malicious errors and outliers, and analyze
their fundamental complexity questions. In particular, we establish lower
bounds on the communication complexity for distributed robust learning
performed on multiple machines, and on the space complexity for robust learning
from streaming data on a single machine. These results demonstrate that gaining
robustness of learning algorithms is usually at the expense of increased
complexities. As far as we know, this work gives the first complexity results
for distributed and online robust PAC learning.