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

Understand

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.

• In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density.
• This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms.
• In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons.