ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time

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

103 citations recorded by the source corpus.

We study the improper learning of multi-layer neural networks. Suppose that the neural network to be learned has $k$ hidden layers and that the $\ell_1$-norm of the incoming weights of any neuron is bounded by $L$. We present a kernel-based method, such that with probability at least $1 - \delta$, it learns a predictor whose generalization error is at most $\epsilon$ worse than that of the neural network. The sample complexity and the time complexity of the presented method are polynomial in the input dimension and in $(1/\epsilon,\log(1/\delta),F(k,L))$, where $F(k,L)$ is a function depending on $(k,L)$ and on the activation function, independent of the number of neurons. The algorithm applies to both sigmoid-like activation functions and ReLU-like activation functions. It implies that any sufficiently sparse neural network is learnable in polynomial time.

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

Beyond Sparsity: Tree Regularization of Deep Models for Interpretability (2017, background): “Other efforts specifically train very sparse networks via L1 penalties (Zhang, Lee, and Jordan 2016) or even binary neural networks (Tang, Hua, and Wang 2017; Rastegari et al. 2016) with the goal of faster computation.”
Deriving Neural Architectures from Sequence and Graph Kernels (2017, methodology): “While some prior work appeals to convex optimization through improper learning (Zhang et al., 2016; Heinemann et al., 2016) (since kernel space is larger), we use the proposed networks as building blocks in typical non-convex but ﬂexible neural network training.”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, neutral): “(e.g. [Choromanska et al., 2014, Sagun et al., 2014, Zhang et al., 2015, Livni et al., 2014]).”
A mean field view of the landscape of two-layer neural networks (2018, neutral): “R (1) d (r) = 1 + 2v(r) + ud(r , r), [14]”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Another line of research [18], [42], [56] focuses on improper learning models using kernel-based approaches.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “etworks. (last) stands for conjugate kernel [20], meaning training only the output layer. (NTK) stands for neural tangent kernel [32] with nite width. We also implemented other direct kernels such as [62] but they perform much worse. Setup. We consider ‘ 2 regression task on synthetic data where fea”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “(Zhang et al., 2016a;b) propose kernel methods to learn the prediction function which is guaranteed to have generalization performance close to that of the NN.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, neutral): “r a linear-separable assumption. Some other works learn neural networks using more delicate algorithms—such as tensor decomposition [4, 13, 25, 43, 72] or tailored algorithm for the problem structure [3, 21, 80]— or design more special activation functions [2, 44, 47, 66]. In this paper, instead, we”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, methodology): “Livni et al. [LSSS14], Zhang et al. [ZLJ16, ZLWJ17], and Daniely et al. [DFS16] study the learnability of special cases of neural networks using ideas from kernel methods.”
SGD Learns the Conjugate Kernel Class of the Network (2017, methodology): “As optimizing the last layer is a convex procedure, the result of Daniely et al. [2016] intuitively shows that the optimization process starts from a favourable point for learning a function in the conjugate kernel space.”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “…treatments of neural network learning algorithms include Lee et al. (1996); Arora et al. (2014); Livni et al. (2014); Janzamin et al. (2015); Safran & Shamir (2016); Zhang et al. (2016); Nguyen & Hein (2017); Zhang et al. (2017); Orhan & Pitkow (2018), although these are less closely related.”
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 practice.”
Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations (2017, methodology): “As noticed by Zhang et al. (2016, 2017b), this is for instance the case for the inverse polynomial kernel.”
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods (2017, methodology): “For matrix C ∈ Rd×k, the j-th column is referred by Cj or cj , j ∈ [k].”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “een studied that achieve polynomial running times under varying assumptions about the network parameters, such as [GKKT16, GK17]. The algorithm of [GK17], returns a “clipped” polynomial. In addition, [ZLJ16] gives polynomial time improperlearning algorithms for multi-layer neural networks under seve”
Convergence Results for Neural Networks via Electrodynamics (2017, methodology): “However, by using a result in [KS06] that learning a neural network with threshold activation functions is equivalent to learning intersection of halfspaces, several authors showed that under certain cryptographic assumptions, depth-two neural networks are not eﬃciently learnable with smooth activat”