# Perceptron Learning Algorithm: what is the probability that the viewed data is linearly separable, after some number of steps?

My understanding is that the Perceptron Learning Algorithm:

• will not converge if the data is not linearly separable.
• might take exponentially many iterations, even if the data is linearly separable.

I'm wondering if, after $k$ steps, anything can be said about the probability that the data is linearly separable?

• Interesting thought, but my hunch is you'll probably have to make some fairly strong assumptions on the distribution of the training data to say anything like this. – Dougal Jul 29 '15 at 18:03