Online Algorithms Cannot Find Isolated Perceptron SolutionsResearch Paper
The binary perceptron asks for a vector of binary weights satisfying random linear inequalities. It is a model of learning with discrete weights and a test case for average-case computational complexity. Its geometry raises a specific algorithmic question: if most solutions have no nearby solutions, which solutions can an algorithm actually find? The pinned…