On Fundamental Limits of Robust Learning
This work addresses the trade-offs in robust learning for distributed and streaming settings, providing foundational complexity results that are novel but incremental in scope.
The paper tackles the fundamental complexity of robust PAC learning from distributed and streaming data with malicious errors, establishing lower bounds on communication and space complexities, showing that robustness increases these complexities.
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.