6a26c75d6a576c94654bfc4dda548c72-Paper.pdf

Forlinear regression, we give a polynomial-time algorithm based on Celis-Dennis-Tapia optimization algorithms. For binary classification, we show how to efficiently implement itusing aproper agnostic learner (i.e., anEmpirical Risk Minimizer) for the class of interest.