Before revision:  In fact our algorithms succeed where convex surrogates failin the sense that we show strong lower bounds for the existing approaches .
After revision:  In fact our algorithms succeed where convex surrogates failin the sense that we show strong lower bounds against Huber regression and more generally any convex M-estimator .