5 papers
On the robustness of noisy solutions in non-convex neural networks
Enrico M. Malatesta, Alessandra Passalacqua, Riccardo Zecchina
Optimization in non-convex neural network models is strongly influenced by the geometry of the solution space: sparse, isolated, point-like clusters are typically algorithmically i…
Collision Resistance of Single-Layer Neural Nets
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix , an…
Are Neural Networks Collision Resistant?
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity…
Dynamical Learning in Deep Asymmetric Recurrent Neural Networks
Davide Badalotti, Carlo Baldassi, Marc Mézard +2
We investigate recurrent neural networks with asymmetric interactions and demonstrate that the inclusion of self-couplings or sparse excitatory inter-module connections leads to th…
Overlap Gap and Computational Thresholds in the Square Wave Perceptron
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional li…