Do Outliers Ruin Collaboration?

Mingda Qiao

Do Outliers Ruin Collaboration?

Mingda Qiao

Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4180-4187, 2018.

Abstract

We consider the problem of learning a binary classifier from

$n$ different data sources, among which at most an

$\eta$ fraction are adversarial. The overhead is defined as the ratio between the sample complexity of learning in this setting and that of learning the same hypothesis class on a single data distribution. We present an algorithm that achieves an

$O(\eta n + \ln n)$ overhead, which is proved to be worst-case optimal. We also discuss the potential challenges to the design of a computationally efficient learning algorithm with a small overhead.

Cite this Paper

BibTeX


@InProceedings{pmlr-v80-qiao18a,
  title = 	 {Do Outliers Ruin Collaboration?},
  author =       {Qiao, Mingda},
  booktitle = 	 {Proceedings of the 35th International Conference on Machine Learning},
  pages = 	 {4180--4187},
  year = 	 {2018},
  editor = 	 {Dy, Jennifer and Krause, Andreas},
  volume = 	 {80},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {10--15 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v80/qiao18a/qiao18a.pdf},
  url = 	 {https://proceedings.mlr.press/v80/qiao18a.html},
  abstract = 	 {We consider the problem of learning a binary classifier from $n$ different data sources, among which at most an $\eta$ fraction are adversarial. The overhead is defined as the ratio between the sample complexity of learning in this setting and that of learning the same hypothesis class on a single data distribution. We present an algorithm that achieves an $O(\eta n + \ln n)$ overhead, which is proved to be worst-case optimal. We also discuss the potential challenges to the design of a computationally efficient learning algorithm with a small overhead.}
}

Endnote

%0 Conference Paper
%T Do Outliers Ruin Collaboration?
%A Mingda Qiao
%B Proceedings of the 35th International Conference on Machine Learning
%C Proceedings of Machine Learning Research
%D 2018
%E Jennifer Dy
%E Andreas Krause	
%F pmlr-v80-qiao18a
%I PMLR
%P 4180--4187
%U https://proceedings.mlr.press/v80/qiao18a.html
%V 80
%X We consider the problem of learning a binary classifier from $n$ different data sources, among which at most an $\eta$ fraction are adversarial. The overhead is defined as the ratio between the sample complexity of learning in this setting and that of learning the same hypothesis class on a single data distribution. We present an algorithm that achieves an $O(\eta n + \ln n)$ overhead, which is proved to be worst-case optimal. We also discuss the potential challenges to the design of a computationally efficient learning algorithm with a small overhead.

APA


Qiao, M.. (2018). Do Outliers Ruin Collaboration?. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4180-4187 Available from https://proceedings.mlr.press/v80/qiao18a.html.

Related Material

Download PDF