Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency

Neural Information Processing Systems 

Our method requires only linear time in input size, and still matches the information theoretical optimal sample complexity up to a data distribution dependent condition number factor.