ReLU Regression with Massart Noise

Abstract

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.

References in corpus (18)

• Poisoning Attacks against Support Vector Machines
• Risk bounds for statistical learning
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Robust Regression via Hard Thresholding
• When is a Convolutional Filter Easy To Learn?
• Reliably Learning the ReLU in Polynomial Time
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• On the Power and Limitations of Random Features for Understanding Neural Networks
• The Computational Complexity of Training ReLU(s)
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Online Robust Regression via SGD on the l1 loss
• On Radial Isotropic Position: Theory and Algorithms
• Approximation Schemes for ReLU Regression
• Efficient Learning of Linear Separators under Bounded Noise
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Forster Decomposition and Learning Halfspaces with Noise