Topology and Geometry of Half-Rectified Network Optimization

By C. Freeman, Joan Bruna. 2016

252 citations recorded by the source corpus.

The loss surface of deep neural networks has recently attracted interest in the optimization and machine learning communities as a prime example of high-dimensional non-convex problem. Some insights were recently gained using spin glass models and mean-field approximations, but at the expense of strongly simplifying the nonlinear nature of the model. In this work, we do not make any such assumption and study conditions on the data distribution and model architecture that prevent the existence of bad local minima. Our theoretical work quantifies and formalizes two important \emph{folklore} facts: (i) the landscape of deep linear networks has a radically different topology from that of deep half-rectified ones, and (ii) that the energy landscape in the non-linear case is fundamentally controlled by the interplay between the smoothness of the data distribution and model over-parametrization. Our main theoretical contribution is to prove that half-rectified single layer networks are asymptotically connected, and we provide explicit bounds that reveal the aforementioned interplay. The conditioning of gradient descent is the next challenge we address. We study this question through the geometry of the level sets, and we introduce an algorithm to efficiently estimate the regularity of such sets on large-scale networks. Our empirical results show that these level sets remain connected throughout all the learning phase, suggesting a near convex behavior, but they become exponentially more curvy as the energy level decays, in accordance to what is observed in practice with very low curvature attractors.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, Optimization & Training, Statistical Learning Theory

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 Computational Theory and Mathematics

In Statistics and Probability

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “Landscape analyses of ReLU activated neural networks for other settings have also been studied in many previous works (Ge et al., 2017; Safran and Shamir, 2016; Zhou and Liang, 2017; Freeman and Bruna, 2016; Hardt and Ma, 2016; Nguyen and Hein, 2018).”
Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs (2018, background): “In recent work Freeman and Bruna [7] theoretically show that local minima of a neural network with one hidden layer and ReLU activations can be connected with a curve along which the loss is upper-bounded by a constant that depends on the number of parameters of the network and the “smoothness of th”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Many papers tried to characterize geometric landscapes of objective functions (Safran & Shamir, 2017; Zhou & Liang, 2017; Freeman & Bruna, 2016; Hardt & Ma, 2016; Nguyen & Hein, 2017; Kawaguchi, 2016; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeﬀele…”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “…landscape of neural networks with different activation functions [Soudry and Hoffer, 2017, Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016, Nguyen and Hein, 2017, Kawaguchi, 2016, Venturi et al., 2018, Soudry and Carmon, 2016, Du and Lee, 2018,…”
Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond (2016, background): “Further considerations on connecting paths between solutions in the weight space of loss functions can be found in Freeman & Bruna (2016).”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “(Freeman & Bruna, 2016) study the landscape of 1NN in terms of topology and geometry, and show that the level set becomes connected as the network is increasingly over-parameterized.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “On the technique side, some of these results try to understand the gradient dynamics [8, 9, 14, 16, 38, 44, 59, 64, 65, 70, 71], while others focus on the geometry properties of the training objective [19, 20, 25, 50, 72].”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “…neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Du and Lee, 2018, Hardt and Ma, 2016, Bartlett et al., 2018, Haeffele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017, Nguyen and Hein, 2017a,b, Zhou and Feng, 2017, Safran and…”
Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets (2019, background): “Freeman and Bruna (2016) showed that for a two-layer net, if it is suﬃciently overparametrized then all the local minimizers are (approximately) connected.”
Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, background): “A number of earlier works (Hardt & Ma, 2016; Freeman & Bruna, 2016; Safran & Shamir, 2018; Nguyen & Hein, 2017; Zhou & Liang, 2017; Du & Lee, 2018) that studied the theoretical properties of NN were based on specific models, and these works attempted to characterize the geometric landscapes of the…”
Git Re-Basin: Merging Models modulo Permutation Symmetries (2022, background): “However, this result for single hidden-layer MLP models is preceded by Freeman & Bruna (2017); Uriot & Izzo (2020).”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, background): “Many papers tried to identify the two desired geometric landscape properties of objective functions for non-linear neural networks (Freeman & Bruna, 2016; Nguyen & Hein, 2017; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeffele & Vidal, 2017).”