Reliably Learning the ReLU in Polynomial Time

Abstract

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 $\mathcal{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 $\mathcal{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.

Cited by in corpus (35)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Understanding Deep Neural Networks with Rectified Linear Units
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Deep Frank-Wolfe For Neural Network Optimization
• Neural networks and rational functions
• Reverse-Engineering Deep ReLU Networks
• Agnostic Learning of a Single Neuron with Gradient Descent
• Statistical-Query Lower Bounds via Functional Gradients
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Learning a Single Neuron with Gradient Methods
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Approximation Schemes for ReLU Regression
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• On the Learnability of Deep Random Networks
• Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time
• Towards Lower Bounds on the Depth of ReLU Neural Networks
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• ReLU Regression with Massart Noise
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Efficient Learning with Arbitrary Covariate Shift
• Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
• From Boltzmann Machines to Neural Networks and Back Again
• Learning Graph Neural Networks with Approximate Gradient Descent