Before revision:  Our approach is based on a novel way to use the sum-of-squares hierarchy in online learning and in the absence of distributional assumptions .
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 .