Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization

Daniel Vainsencher, Shie Mannor, Huan Xu
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1849-1881, 2017.

Abstract

We consider learning in the presence of arbitrary noise that can overwhelm the signal in terms of magnitude on a fraction of data points observed (aka outliers). Standard approaches based on minimizing empirical loss can fail miserably and lead to arbitrary bad solutions in this setting. We propose an approach that iterates between finding a solution with minimal empirical loss and re-weighting the data, reinforcing data points where the previous solution works well. We show that our approach can handle arbitrarily large noise, is robust as having a non-trivial breakdown point, and converges linearly under certain conditions. The intuitive idea of our approach is to automatically exclude “difficult” data points from model fitting. More importantly (and perhaps surprisingly), we validate this intuition by establishing guarantees for generalization and iteration complexity that \em essentially ignore the presence of outliers

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-vainsencher17a, title = {Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization}, author = {Vainsencher, Daniel and Mannor, Shie and Xu, Huan}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1849--1881}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/vainsencher17a/vainsencher17a.pdf}, url = {https://proceedings.mlr.press/v65/vainsencher17a.html}, abstract = { We consider learning in the presence of arbitrary noise that can overwhelm the signal in terms of magnitude on a fraction of data points observed (aka outliers). Standard approaches based on minimizing empirical loss can fail miserably and lead to arbitrary bad solutions in this setting. We propose an approach that iterates between finding a solution with minimal empirical loss and re-weighting the data, reinforcing data points where the previous solution works well. We show that our approach can handle arbitrarily large noise, is robust as having a non-trivial breakdown point, and converges linearly under certain conditions. The intuitive idea of our approach is to automatically exclude “difficult” data points from model fitting. More importantly (and perhaps surprisingly), we validate this intuition by establishing guarantees for generalization and iteration complexity that \em essentially ignore the presence of outliers } }
Endnote
%0 Conference Paper %T Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization %A Daniel Vainsencher %A Shie Mannor %A Huan Xu %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-vainsencher17a %I PMLR %P 1849--1881 %U https://proceedings.mlr.press/v65/vainsencher17a.html %V 65 %X We consider learning in the presence of arbitrary noise that can overwhelm the signal in terms of magnitude on a fraction of data points observed (aka outliers). Standard approaches based on minimizing empirical loss can fail miserably and lead to arbitrary bad solutions in this setting. We propose an approach that iterates between finding a solution with minimal empirical loss and re-weighting the data, reinforcing data points where the previous solution works well. We show that our approach can handle arbitrarily large noise, is robust as having a non-trivial breakdown point, and converges linearly under certain conditions. The intuitive idea of our approach is to automatically exclude “difficult” data points from model fitting. More importantly (and perhaps surprisingly), we validate this intuition by establishing guarantees for generalization and iteration complexity that \em essentially ignore the presence of outliers
APA
Vainsencher, D., Mannor, S. & Xu, H.. (2017). Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1849-1881 Available from https://proceedings.mlr.press/v65/vainsencher17a.html.

Related Material