Before revision:  Our approach is based on a novel alternating minimization scheme that interleaves ordinary least-squares with a semidefinite program for finding appropriate reweightings of the distribution . Moreover we give extensions of our main results to infinite dimensional settings where the feature vectors are represented implicitly via a kernel map.
After revision:  Our approach is based on a novel alternating minimization scheme that interleaves ordinary least-squares with a semidefinite program for finding appropriate reweightings of the distribution under a spectral constraint. Our results obtain essentially optimal dependence on the contamination level \eta, reach the optimal breakdown point, and naturally apply to infinite dimensional settings where the feature vectors are represented implicitly via a kernel map.