Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

Emmanuel Abbe, Shuangping Li, Allan Sly

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard…