Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes

Abstract

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 novel measure, which we call 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 which 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 new 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.

31 pages (14 main text, 18 appendix), 12 figures (6 main text, 6 appendix)

References in corpus (9)

• Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Fractal free energy landscapes in structural glasses
• Finding undetected protein associations in cell signaling by belief propagation
• Efficient supervised learning in networks with binary synapses
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Locked constraint satisfaction problems
• Generalization learning in a perceptron with binary synapses

Cited by in corpus (71)

• Machine learning and the physical sciences
• A trans-disciplinary review of deep learning research for water resources scientists
• Fast Automated Analysis of Strong Gravitational Lenses with Convolutional Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Shaping the learning landscape in neural networks around wide flat minima
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
• Explorability and the origin of Network Sparsity in Living Systems
• Statistical Criticality arises in Most Informative Representations
• An Optimal Control Approach to Deep Learning and Applications to Discrete-Weight Neural Networks
• Quantum algorithm for energy matching in hard optimization problems
• Mean-field inference methods for neural networks
• Unveiling the structure of wide flat minima in neural networks
• Entropic gradient descent algorithms and wide flat minima
• On the different regimes of Stochastic Gradient Descent
• Learning through atypical "phase transitions" in overparameterized neural networks
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Glassy nature of the hard phase in inference problems
• Biased landscapes for random Constraint Satisfaction Problems
• Generating dense packings of hard spheres by soft interaction design
• Quantifying Relevance in Learning and Inference
• On the role of synaptic stochasticity in training low-precision neural networks
• Counting the learnable functions of structured data
• Parle: parallelizing stochastic gradient descent
• Beyond the storage capacity: data driven satisfiability transition
• Fundamental problems in statistical physics XIV: Lecture on Machine Learning
• Clustering of solutions in the symmetric binary perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Dual time scales in simulated annealing of a two-dimensional Ising spin glass
• Deep learning via message passing algorithms based on belief propagation
• Arrangement of nearby minima and saddles in the mixed spherical energy landscapes
• A theory of non-equilibrium local search on random satisfaction problems
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Eight challenges in developing theory of intelligence
• On the Atypical Solutions of the Symmetric Binary Perceptron
• SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
• Finding the Needle in the Haystack with Convolutions: on the benefits of architectural bias
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Statistical mechanics of the maximum-average submatrix problem
• Partial local entropy and anisotropy in deep weight spaces
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• How neural networks find generalizable solutions: Self-tuned annealing in deep learning
• Optimization of the dynamic transition in the continuous coloring problem
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• A method to reduce the rejection rate in Monte Carlo Markov Chains
• SWAP algorithm for lattice spin models
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Some Remarks on Replicated Simulated Annealing
• Reinforced stochastic gradient descent for deep neural network learning
• On the topology of solutions to random continuous constraint satisfaction problems
• Stochastic Gradient Descent and Anomaly of Variance-flatness Relation in Artificial Neural Networks
• Optimization of neural networks via finite-value quantum fluctuations
• Gradient dynamics in reinforcement learning
• Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
• Network Dynamics-Based Framework for Understanding Deep Neural Networks
• Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry
• Interacting Copies of Random Constraint Satisfaction Problems
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Native state of natural proteins optimises local entropy
• SGB: Stochastic Gradient Bound Method for Optimizing Partition Functions
• Maximal Relevance and Optimal Learning Machines