Poster
Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
Surbhi Goel · Sushrut Karmalkar · Adam Klivans
East Exhibition Hall B, C #235
Keywords: [ Hardness of Learning and Approximations ] [ Theory ] [ Computational Complexity ]
[
Abstract
]
Abstract:
We consider the problem of computing the best-fitting ReLU with
respect to square-loss on a training set when the examples have been
drawn according to a spherical Gaussian distribution (the labels can
be arbitrary). Let be the population loss of the
best-fitting ReLU. We prove:
Prior work due to Soltanolkotabi \cite{soltanolkotabi2017learning} showed that gradient descent {\em can} find the best-fitting ReLU with respect to Gaussian marginals, if the training set is {\em exactly} labeled by a ReLU.
Live content is unavailable. Log in and register to view live content