ReLU Regression with Massart Noise
  We study the fundamental problem of ReLU regression, where the goal is to fit
Rectified Linear Units (ReLUs) to data. This supervised learning task is
efficiently solvable in the realizable setting, but is known to be
computationally hard with adversarial label noise. In this work, we focus on
ReLU regression in the Massart noise model, a natural and well-studied
semi-random noise model. In this model, the label of every point is generated
according to a function in the class, but an adversary is allowed to change
this value arbitrarily with some probability, which is {\em at most} $\eta <
1/2$. We develop an efficient algorithm that achieves exact parameter recovery
in this model under mild anti-concentration assumptions on the underlying
distribution. Such assumptions are necessary for exact recovery to be
information-theoretically possible. We demonstrate that our algorithm
significantly outperforms naive applications of $\ell_1$ and $\ell_2$
regression on both synthetic and real data.
