When low-loss paths make a binary neuron trainable: detecting algorithmic transitions with the connected ensemble

We study the connected ensemble, a statistical-mechanics framework that characterizes the formation of low-loss paths in rugged landscapes. First introduced in a previous paper, this ensemble allows one to identify when a network can be trained on a simple task and which minima should be targeted during training. We apply this new framework to the symmetric binary perceptron model (SBP), and study how its typical {connected} minima behave. We show that {connected} minima exist only above a critical threshold ${\kappa }_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}}$, or equivalently below a critical constraint density ${\alpha }_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}}$. This defines a parameter range in which training the network is easy, as local algorithms can efficiently access this connected manifold. We also highlight that these minima become increasingly robust and closer to one another as the task on which the network is trained becomes more difficult.