Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes

By Carlo Baldassi, Christian Borgs, Jennifer Tour Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, Riccardo Zecchina. 2016

183 citations recorded by the source corpus.

Significance Artificial neural networks are some of the most widely used tools in data science. Learning is, in principle, a hard problem in these systems, but in practice heuristic algorithms often find solutions with good generalization properties. We propose an explanation of this good performance in terms of a nonequilibrium statistical physics framework: We show that there are regions of the optimization landscape that are both robust and accessible and that their existence is crucial to achieve good performance on a class of particularly difficult learning problems. Building on these results, we introduce a basic algorithmic scheme that improves existing optimization algorithms and provides a framework for further research on learning in neural networks. In artificial neural networks, learning from data is a computationally demanding task in which a large number of connection weights are iteratively tuned through stochastic-gradient-based heuristic processes over a cost function. It is not well understood how learning occurs in these systems, in particular how they avoid getting trapped in configurations with poor computational performance. Here, we study the difficult case of networks with discrete weights, where the optimization landscape is very rough even for simple architectures, and provide theoretical and numerical evidence of the existence of rare—but extremely dense and accessible—regions of configurations in the network weight space. We define a measure, the robust ensemble (RE), which suppresses trapping by isolated configurations and amplifies the role of these dense regions. We analytically compute the RE in some exactly solvable models and also provide a general algorithmic scheme that is straightforward to implement: define a cost function given by a sum of a finite number of replicas of the original cost function, with a constraint centering the replicas around a driving assignment. To illustrate this, we derive several powerful algorithms, ranging from Markov Chains to message passing to gradient descent processes, where the algorithms target the robust dense states, resulting in substantial improvements in performance. The weak dependence on the number of precision bits of the weights leads us to conjecture that very similar reasoning applies to more conventional neural networks. Analogous algorithmic schemes can also be applied to other optimization problems.

Subfields: Artificial Intelligence

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

Citations in the corpus

Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “It was found that solutions of discrete learning problems that generalize well belong to dense clusters in the weight space (Baldassi et al., 2015; 2016).”
Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach (2018, background): “This concept has also been widely studied (e.g., Langford, 2002; Langford & Caruana, 2002; Hinton & van Camp, 1993; Hochreiter & Schmidhuber, 1997; Baldassi et al., 2015; 2016; Chaudhari et al., 2017; Keskar et al., 2017; Dziugaite & Roy, 2017; Neyshabur et al., 2018).”
Comparing dynamics: deep neural networks versus glassy systems (2018, background): “A complementary point of view, proposed in (Baldassi et al., 2016), is that there exist rare and wide minima which have large basins of attraction and are reached without any substantial barrier crossing by the training dynamics.”
On the energy landscape of deep networks (2015, background): “…of various models of neural networks, e.g., deep linear networks (Saxe et al., 2013), deep Gaussian processes (Duvenaud et al., 2014), spin glasses (Choromanska et al., 2014), tensor factorization (Haeffele and Vidal, 2015; Janzamin et al., 2015), robust ensembles (Baldassi et al., 2016) etc.”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, background): “Recently, the study of random instances of neural networks have emerged as a key ingredient in understanding the performance of deep learning algorithms [29, 30].”
Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning (2018, methodology): “This includes: work on large-batch learning and the generalization gap [148, 72, 64, 57, 67, 131, 66, 146, 94, 151, 152]; work on Energy Landscape approaches to NN training [70, 149, 44, 123, 30, 29, 27, 65, 47, 12, 104, 150, 50, 83, 82, 95]; work on using weight matrices or properties of weight mat”
Parle: parallelizing stochastic gradient descent (2017, methodology): “Using different techniques, the two objectives can be shown equivalent under different approximations (Baldassi et al., 2016a).”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors (2017, background): “…argue informally that maximizing the local entropy leads to “ﬂat minima” in the empirical risk surface, which several authors (Hinton & van Camp, 1993; Hochre-iter & Schmidhuber, 1997; Baldassi et al., 2015; 2016) w (cid:48) , µ ← w 3: for i ∈ { 1 ,..., L } do (cid:46) Run SGLD for L iterations.”
A Transdisciplinary Review of Deep Learning Research and Its Relevance for Water Resources Scientists (2017, background): “DL algorithms have shown a generational leap in predictive capability which some argued as unreasonable (Baldassi et al., 2016; C. Sun et al., 2017).”