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.
翻译:我们研究ReLU回归的根本问题, 目标是将校正线性单位( ReLUs) 与数据相匹配。 这一受监督的学习任务在可实现的环境下是有效的, 可以在可实现的环境下有效溶解, 但已知是用对抗性标签噪音来计算硬性。 在这项工作中, 我们集中研究Massart噪音模型中的ReLU回归, 这是一种自然的和经过深思熟虑的半随机噪音模型。 在这个模型中, 每个点的标签都是根据该类的函数生成的, 但允许对手任意改变这个值, 可能有些可能性, 最多是 $\eta < 1/2 美元 。 我们开发一种高效的算法, 在对基本分布进行温和的反集中假设的情况下实现该模型的精确参数恢复。 这种假设对于准确恢复是信息- 理论上可能的。 我们证明我们的算法大大超出合成数据和真实数据的天真应用值1美元和 $\ =2美元。