# Breaking the Curse of Dimensionality with Convex Neural Networks

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

## Key facts

- Cited by 331 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2014.

## Built on by (most cited first, 30 of 331)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie](https://mlsanity.com/paper/2103.04715/) (2021)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [GradMax: Growing Neural Networks using Gradient Information](https://mlsanity.com/paper/2201.05125/) (2022)
- [The alignment property of SGD noise and how it helps select flat minima: A stability analysis](https://mlsanity.com/paper/2207.02628/) (2022)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Understanding neural networks with reproducing kernel Banach spaces](https://mlsanity.com/paper/2109.09710/) (2021)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness](https://mlsanity.com/paper/2205.00403/) (2022)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks](https://mlsanity.com/paper/2109.08844/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Numerical analysis of physics-informed neural networks and related models in physics-informed machine learning](https://mlsanity.com/paper/2402.10926/) (2024)
- [How to Understand Masked Autoencoders](https://mlsanity.com/paper/2202.03670/) (2022)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)

## Abstract (arXiv)

We consider neural networks with a single hidden layer and non-decreasing homogeneous activa-tion functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of ob-servations. In addition, we provide a simple geometric interpretation to the non-convex problem of addition of a new unit, which is the core potentially hard computational element in the framework of learning from continuously many basis functions. We provide simple conditions for convex relaxations to achieve the same generalization error bounds, even when constant-factor approxi-mations cannot be found (e.g., because it is NP-hard such as for the zero-homogeneous activation function). We were not able to find strong enough convex relaxations and leave open the existence or non-existence of polynomial-time algorithms.