License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.3
URN: urn:nbn:de:0030-drops-88294
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8829/
Go to the corresponding LIPIcs Volume Portal

Moitra, Ankur

Robustness Meets Algorithms (Invited Talk)

pdf-format:
LIPIcs-SWAT-2018-3.pdf (0.2 MB)

Abstract

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model but even when their assumptions are violated. Unfortunately in high-dimensions, being provably robust and efficiently computable are often at odds with each other. In this talk, we give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian which is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute, or could tolerate only an inverse polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, it turns out to be highly practical in a variety of settings.

BibTeX - Entry

@InProceedings{moitra:LIPIcs:2018:8829,
  author =	{Ankur Moitra},
  title =	{{Robustness Meets Algorithms (Invited Talk)}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8829},
  URN =		{urn:nbn:de:0030-drops-88294},
  doi =		{10.4230/LIPIcs.SWAT.2018.3},
  annote =	{Keywords: robust estimators, machine learning algorithms}
}

Keywords: robust estimators, machine learning algorithms
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI