Learning Halfspaces and Neural Networks with Random Initialization

By Yuchen Zhang, Jason D. Lee, Martin J. Wainwright, Michael I. Jordan. 2015

39 citations recorded by the source corpus.

We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are $L$-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk $\epsilon>0$. The time complexity is polynomial in the input dimension $d$ and the sample size $n$, but exponential in the quantity $(L/\epsilon^2)\log(L/\epsilon)$. These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin $\gamma>0$, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin $\Omega(\gamma)$. As a consequence, the algorithm achieves arbitrary generalization error $\epsilon>0$ with ${\rm poly}(d,1/\epsilon)$ sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability $\eta<1/2$.

Subfields: Artificial Intelligence

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

Citations in the corpus

Robust Large Margin Deep Neural Networks (2016, methodology): “We focus on DNN without the pooling stage as often done in the literature, e.g. [15, 23], and defer the study of DNN with pooling layers to a future study.”
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.”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Various recent papers show that poly-time learning is possible in the case that the the learnt function can be realized by a neural network with certain (usually fairly strong) restrictions on the weights [23, 34, 33, 35], or under the assumption that the data is generated by a generative model that”
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].”
Convergence Results for Neural Networks via Electrodynamics (2017, methodology): “Kernel methods, ridge regression, and even boosting were explored for regularized neural networks with smooth activation functions in [SSSS11, ZLWJ15, ZLJ16].”
Escaping Saddles with Stochastic Gradients (2018, background): “As a result, Assumption 1 (CNC) holds for stochastic (5)This assumption is equivalent to assuming the random variable z lies inside the unit sphere, which is common in learning halfspace (Zhang et al., 2015).”
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.”
A Provably Correct Algorithm for Deep Learning that Actually Works (2018, background): “The works of [11,17,18] show polynomial-time algorithms aimed at learning deep models, but that seem far from performing well in”
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].”
Convexified Convolutional Neural Networks (2016, methodology): “[47] propose a polynomial-time ensemble method for learning fully-connected neural networks, but their approach handles neither parameter sharing nor the convolutional setting.”
Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization (2018, methodology): “This is unfortunate since Gradient Descent converges linearly in the quadratic least-squares setting but only sublinearly on general Learning Halfspace problems (Zhang et al., 2015).”
On the Quality of the Initial Basin in Overspecified Neural Networks (2015, result): “Other works, such as (Arora et al., 2014; Andoni et al., 2014; Janzamin et al., 2015; Zhang et al., 2015) and some of the results in (Livni et al.”
Reliably Learning the ReLU in Polynomial Time (2016, methodology): “Given the above transformation to a polynomial network and associated error bounds, we apply the main theorem of Zhang et al. (2016a) combined with the clipping technique from Section 3 to obtain the following result:”