A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networks
Not on the map. Why?
Abstract (arXiv)
To fit sparse linear associations, a LASSO sparsity inducing penalty with a single hyperparameter provably allows to recover the important features (needles) with high probability in certain regimes even if the sample size is smaller than the dimension of the input vector (haystack). More recently learners known as artificial neural networks (ANN) have shown great successes in many machine learning tasks, in particular fitting nonlinear associations. Small learning rate, stochastic gradient descent algorithm and large training set help to cope with the explosion in the number of parameters present in deep neural networks. Yet few ANN learners have been developed and studied to find needles in nonlinear haystacks. Driven by a single hyperparameter, our ANN learner, like for sparse linear associations, exhibits a phase transition in the probability of retrieving the needles, which we do not observe with other ANN learners. To select our penalty parameter, we generalize the universal threshold of Donoho and Johnstone (1994) which is a better rule than the conservative (too many false detections) and expensive cross-validation. In the spirit of simulated annealing, we propose a warm-start sparsity inducing algorithm to solve the high-dimensional, non-convex and non-differentiable optimization problem. We perform precise Monte Carlo simulations to show the effectiveness of our approach.
Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 20 of its 63 references that are in the map. First posted on arXiv 21 Jan 2022.
Builds on
20 of 63 references.
References · 20
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 510
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 411
- 2017High-dimensional dynamics of generalization error in neural networkscited by 241
- 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
- 2019Deep Neural Network Approximation Theorycited by 93
- 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 91
- 2019Scaling description of generalization with number of parameters in deep learningcited by 83
- 2019The Difficulty of Training Sparse Neural Networkscited by 62
- 2020The gap between theory and practice in function approximation with deep neural networkscited by 54
- 2021Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problemcited by 53
- 2017Sparse-Input Neural Networks for High-dimensional Nonparametric Regression and Classificationcited by 39
- 2021Consistent Sparse Deep Learning: Theory and Computationcited by 27
8 more
- 2020Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Datacited by 22
- 2014Memory Bounded Deep Convolutional Networkscited by 17
- 2020Directional Pruning of Deep Neural Networkscited by 16
- 2021Truly Sparse Neural Networks at Scalecited by 16
- 2021The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learningcited by 12
- 2018Make ℓ1 Regularization Effective in Training Sparse CNNcited by 4
- 2017Regularising Non-linear Models Using Feature Side-informationcited by 3
- 2018Model selection with lasso-zero: adding straw to the haystack to better find needlescited by 2
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.