Breaking the Curse of Dimensionality with Convex Neural Networks

By Francis R. Bach. 2014

818 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Model Architectures, Optimization & Training

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 Model Architectures

In Optimization & Training

Citations in the corpus

When do neural networks outperform kernel methods? (2020, background): “target functions f∗ that can be represented and possibly efficiently learnt using neural networks, but not in the corresponding RKHS [32, 6, 17, 16, 1, 2].”
Robust Large Margin Deep Neural Networks (2016, background): “s and may be linear or non-linear. With the remarkable success of DNN, there have been multiple attempts to provide theoretical foundations for the representation power and learning complexity of DNN [2, 4, 5, 6, 13, 20]. An important theorethical aspect of DNN is the effect of their architecture an”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, background): “There are also interesting questions of network architectures representing, and adapting to, the underlying function, and if these can be learned from the data (Bach, 2017; Dou and Liang, 2020).”
Representing smooth functions as compositions of near-identity functions with implications for deep network optimization (2018, methodology): “Such algorithms have been studied for two-layer networks; see (Bach, 2014; Bengio et al., 2006; Lee et al., 1996).”
Batch Stationary Distribution Estimation (2020, background): “Nguyen et al. (2008, Theorem 2) show that, under mild conditions, the statistical error can be bounded in rate O ⇣ ⌘ in terms of Hellinger distance ( � denotes the exponent in the bracket entropy of the RKHS), while the approximation error will depend on the RKHS (Bach, 2014).”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, neutral): “We consider the error between τ̂ and τ∗ using standard arguments (Shalev-Shwartz & Ben-David, 2014; Bach, 2014), i.e., d (τ̂ , τ∗) := J (τ̂)− J (τ∗) .”
In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning (2014, neutral): “Indeed, for matrix factorizations (i.e. with linear activations), such a group-lasso regularized formulation is known to be equivalent to the trace norm (3) (see Argyriou et al., 2007).”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “The works by (Bach, 2014) and (Bengio et al., 2005) are also in this direction.”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “An admissible choice of regularizer here would be the (semi-convex) function V (w, θ) = |w| · |θ| [4].”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Several previous papers [24, 10, 28, 27, 25, 32, 18, 26, 6, 5, 16, 2] investigated such associations, but in a more restricted settings (i.”
Norm-Based Capacity Control in Neural Networks (2015, background): “A two-layer network of this form with RELU activation was also considered by Bach (2014), who studied its approximation ability and suggested heuristics for learning it.”
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, background): “The closeness of learned weights to initialization in the over-parametrized setting can be understood by considering the limiting case as the number of hidden units go to inﬁnity, as considered in Bengio et al. [5] and Bach [2].”
Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys (2018, neutral): “Our approach is complementary to another line of work that attempts to characterize the landscape by studying its critical points [16, 19, 15, 12, 24], and is related to recent work that also explores convexifications of neural networks [2, 28, 4].”
Frequency Bias in Neural Networks for Input of Non-Uniform Density (2020, methodology): “(Bach, 2017; Basri et al., 2019; Bietti & Mairal, 2019; Cao et al., 2019; Xie et al., 2017) For a deep FC network the NTK is expressed by the following recursion (Arora et al., 2019a; Jacot et al., 2018) Here ˙ σ ( · ) denotes the step function (i.e., the derivative of the ReLU function).”
On the Discrimination-Generalization Tradeoff in GANs (2017, background): “In particular, Proposition 6 of Bach (2017) allows us to derive the decay rate of approximating bounded Lipschitz functions with rectiﬁed neurons, yielding a bound between BL distance and neural distance. where ˜ O denotes the big-O notation ignoring the logarithm factor.”