Reliably Learning the ReLU in Polynomial Time
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:10041042, 2017.
Abstract
We give the first dimensionefficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form $\mathbf{x} \mapsto \mathsf{max}(0, \mathbf{w} ⋅\mathbf{x})$ with $\mathbf{w} ∈\mathbb{S}^n1$. Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade and Mansour (2012) where the learner is given access to a distribution $\mathcal{D}$ on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the falsepositive rate and the loss on inputs given positive labels by $\mathcal{D}$, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomialtime (in $n$) with respect to \em any distribution on $\mathbb{S}^n1$ (the unit sphere in $n$ dimensions) and for any error parameter $ε= Ω(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 $Ω(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 constantdepth networks of ReLU with fixed polynomialdependence in the dimension. For depth2 networks of sigmoids, we obtain the first algorithms that have a polynomial dependency in \em all parameters. Our techniques combine kernel methods and polynomial approximations with a “dualloss” approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for “convex piecewiselinear fitting” and the first efficient algorithms for noisy polynomial reconstruction of lowweight polynomials on the unit sphere.
Related Material


