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

arXiv: https://arxiv.org/abs/1510.03528 · HTML: https://mlsanity.com/paper/1510.03528/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2015.

## Built on by (most cited first, 16 of 16)

- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [A spectral-based analysis of the separation between two-layer neural networks and linear methods](https://mlsanity.com/paper/2108.04964/) (2021)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Learning by Active Forgetting for Neural Networks](https://mlsanity.com/paper/2111.10831/) (2021)
- [Is Stochastic Gradient Descent Near Optimal?](https://mlsanity.com/paper/2209.08627/) (2022)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)
- [Convexified Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2505.18289/) (2025)

## Abstract (arXiv)

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 ℓ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 - δ, it learns a predictor whose generalization error is at most ε 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/ε,log(1/δ),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.