Breaking the Curse of Dimensionality with Convex Neural Networks

Abstract

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.

References in corpus (5)

• On the Number of Linear Regions of Deep Neural Networks
• Consistency of the group Lasso and multiple kernel learning
• Component selection and smoothing in multivariate nonparametric regression
• Learning From An Optimization Viewpoint
• Computational Aspects of the Hausdorff Distance in Unbounded Dimension

Cited by in corpus (55)

• Benign Overfitting in Linear Regression
• Robust Large Margin Deep Neural Networks
• Learning New Physics from a Machine
• A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations
• Review and Comparison of Commonly Used Activation Functions for Deep Neural Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis
• PINNup: Robust neural network wavefield solutions using frequency upscaling and neuron splitting
• Supervised learning from noisy observations: Combining machine-learning techniques with data assimilation
• Implicit Regularization in Deep Learning
• Perspectives on adaptive dynamical systems
• Combining machine learning and data assimilation to forecast dynamical systems from noisy partial observations
• Full error analysis for the training of deep neural networks
• What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory
• Ensuring thermodynamic consistency with invertible coarse-graining
• Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks
• Deep Learning Meets Sparse Regularization: A Signal Processing Perspective
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• Greedy Layerwise Learning Can Scale to ImageNet
• Transport Analysis of Infinitely Deep Neural Network
• On the Generalization Error Bounds of Neural Networks under Diversity-Inducing Mutual Angular Regularization
• Approximation Properties of Deep ReLU CNNs
• Learning from Conditional Distributions via Dual Embeddings
• Convexified Convolutional Neural Networks
• Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
• Representing smooth functions as compositions of near-identity functions with implications for deep network optimization
• Learning Multivariate New Physics
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• Batch Stationary Distribution Estimation
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie
• Random Features for Compositional Kernels
• Relative stability toward diffeomorphisms indicates performance in deep nets
• On architectural choices in deep learning: From network structure to gradient convergence and parameter estimation
• Support Localization and the Fisher Metric for off-the-grid Sparse Regularization
• Deep Online Convex Optimization with Gated Games
• A Statistical Theory of Deep Learning via Proximal Splitting
• Variable Selection with Rigorous Uncertainty Quantification using Deep Bayesian Neural Networks: Posterior Concentration and Bernstein-von Mises Phenomenon
• Regression as Classification: Influence of Task Formulation on Neural Network Features
• Towards optimal sensor placement for inverse problems in spaces of measures
• Deep Online Convex Optimization by Putting Forecaster to Sleep
• Weighted variation spaces and approximation by shallow ReLU networks
• Deep Historical Borrowing Framework to Prospectively and Simultaneously Synthesize Control Information in Confirmatory Clinical Trials with Multiple Endpoints
• Signal reconstruction using determinantal sampling
• Learning and Generalization in RNNs
• Deep Neural Networks Guided Ensemble Learning for Point Estimation
• Learning Infinite RBMs with Frank-Wolfe
• Approximation of Functionals by Neural Network without Curse of Dimensionality
• Probabilistic partition of unity networks for high-dimensional regression problems
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• Function approximation with zonal function networks with activation functions analogous to the rectified linear unit functions
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
• Nearly Optimal Learning using Sparse Deep ReLU Networks in Regularized Empirical Risk Minimization with Lipschitz Loss