Efficient Co-Training of Linear Separators under Weak Dependence


Avrim Blum, Yishay Mansour ;
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:302-318, 2017.


We develop the first polynomial-time algorithm for co-training of homogeneous linear separators under \em weak dependence, a relaxation of the condition of independence given the label. Our algorithm learns from purely unlabeled data, except for a single labeled example to break symmetry of the two classes, and works for any data distribution having an inverse-polynomial margin and with center of mass at the origin.

Related Material