Reliably Learning the ReLU in Polynomial Time

We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form x mapsto max(0, w · x) with w ∈ mathbbSn-1. Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution calD on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by calD, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in n) with respect to any distribution on mathbbSn-1 (the unit sphere in n dimensions) and for any error parameter ε = Omega(1/log n) (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where ε must be Omega(1) and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a "dual-loss" approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for "convex piecewise-linear fitting" and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere.