Online Robust Learning Using the Radon Point

Published in MSc thesis, University of Bonn, 2017

This thesis analyzes a novel approach for model synchronization in distributed online learning from noisy data streams. The proposed approach combines weak hypotheses that have been computed locally by replacing them with their Radon point (akin to the center point, or median in 1-dim). These hypotheses may be learned by a wide range of online learning algorithms thus making the approach black-box. The work encompasses both the theoretical and empirical aspects of the method. The theoretical analysis focuses on proving probabilistic guarantees on the error bound. We show that on noise-free streams, the approach satisfies strong probabilistic error guarantees within the framework of PAC (Probably Approximately Correct) learning. Additionally, under strict assumptions, it provides a method for converting regret bounds of standard online learning algorithms to PAC error bounds. The empirical part focuses on evaluating the practical aspect of the approach. It shows that the proposed approach outperforms state of the art approaches on noisy data streams.