Reliably Learning the ReLU in Polynomial Time

By Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler. 2016

131 citations recorded by the source corpus.

We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form $\mathbf{x} \mapsto \max(0, \mathbf{w} \cdot \mathbf{x})$ with $\mathbf{w} \in \mathbb{S}^{n-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 $\cal{D}$ 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 $\cal{D}$, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in $n$) with respect to any distribution on $\mathbb{S}^{n-1}$ (the unit sphere in $n$ dimensions) and for any error parameter $\epsilon = \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 $\epsilon$ 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.

Subfields: Artificial Intelligence, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade (Daniely, 2016; Daniely & Shalev-Shwartz, 2016; Goel et al., 2017; Klivans & Sherstov, 2009; Livni et al., 2014; Manurangsi & Reichman, 2018; Song et al., 2017).”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “Fortunately, we also show that if g is large, by doing SGD, it will keep decreasing until it is small enough while maintaining the weight W in a nice region.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, methodology): “We acknowledge a different line of research using kernels as improper learners to learn the concept class of neural networks [22, 23, 36, 54].”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “The recent empirical success of NNs has boosted their theoretical analyses (Feng et al., 2016; Balduzzi, 2016; Bal-duzzi et al., 2016; Sagun et al., 2016; Andoni et al., 2014; Arora et al., 2017; Goel et al., 2017).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “With some additional assumptions, many works tried to design algorithms that provably learn a neural network with polynomial time and sample complexity [Goel et al., 2016, Zhang et al., 2015, Sedghi and Anandkumar, 2014, Janzamin et al., 2015, Goel and Klivans, 2017a,b].”
Understanding Deep Neural Networks with Rectified Linear Units (2016, background): “A related algorithm for improperly learning ReLU networks with a single hidden layer has been recently obtained by Goel et al [10], with running time n O (1) 2 O ( √ w/(cid:15) ) , where (cid:15) is the error bound on the expected loss ( n, w are the number of inputs and size of the network, respect”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “While computing a tensor decomposition is NP-hard in general Hillar and Lim (2013), there is a plethora of work on special cases, where computing such decompositions is tractable Bhaskara et al.”
Learning One Convolutional Layer with Overlapping Patches (2018, background): “For example, in the non-realizable (agnostic) setting, it is known that learning a single ReLU (even for bounded distributions and unit norm hidden weight vectors) with respect to square-loss is as hard as learning sparse parity with noise (Goel et al., 2016), a notoriously difficult problem from co”
Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, background): “Nevertheless, a vast literature (Kalai and Sastry, 2009; Kakade et al., 2011; Sedghi and Anandkumar, 2014; Janzamin et al., 2015; Zhang et al., 2015; Goel et al., 2016; Arora et al., 2016) developed ad hoc algorithms that can learn neural networks with provable guarantees.”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, methodology): “Learning a neural network is known to be a hard problem even in some simple settings (Goel et al., 2016; Brutzkus & Globerson, 2017), so we need to make assumptions on the network structure or the input distributionD, or both.”
The Computational Complexity of Training ReLU(s) (2018, methodology): “Speciﬁcally, while we prove NP-hardness results for training ReLUs, our learning results (paralleling those of [GKKT17] for improper learning) show that eﬃcient training 2 (up to small additive errors) is possible when weights and inputs of bounded norms are concerned.”
Learning ReLUs via Gradient Descent (2017, methodology): “would like to thank Adam Klivans and Matus Telgarsky for discussions related to [6] and the Isotron algorithm.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “(2016) to obtain results for learning sparse neural networks with certain smooth activations, and Goel et al. (2016) used a similar approach in conjunction with general tools from approximation theory to obtain learning results for a large class of nonlinear activations including ReLU and Sigmoid. O”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “With some additional assumptions, many works tried to design algorithms that provably learn a neural network ( Goel et al., 2016; Sedghi and Anandkumar, 2014; Janzamin et al., 2015).”
When is a Convolutional Filter Easy To Learn? (2017, background): “With some additional assumptions, many works tried to design algorithms that provably learn a neural network with polynomial time and sample complexity [Goel et al., 2016, Zhang et al., 2015, Sedghi and Anandkumar, 2014, Janzamin et al., 2015].”