Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals

Here we consider the more realistic scenario of empirical risk minimization or learning a ReLU with noise (often referred to as agnostically learning a ReLU). We assume that a learner has access to a training set from a joint distribution D on Rd R where the marginal distribution on Rd is Gaussian but the distribution on the labels can be arbitrary within [0,1].