Suppose I have a linearly separable dataset, divide into training and validation sets. Will a perceptron learned on the training dataset be guaranteed to have no error on the training dataset and on the validation dataset?
Your question, as I understand it, is this: Given a linearly separable data set, if a perceptron is trained on any subset of that data set, is the perceptron guaranteed to have a) 100% training accuracy and b) 100% test accuracy on the remaining data not in the training set?
a) Since the data set is linearly separable, any subset of the data is also linearly separable. Thus, the perceptron is guaranteed to converge to a perfect solution on the training set. (https://en.wikipedia.org/wiki/Perceptron#Convergence)
b) No. Consider the following classification problem as a counterexample. The graph below shows a very simple linearly separable data set consisting of two classes of data points — red points and blue points. The black line highlights the linear separableness of the data.
Now, since any subset of the points can be used for our training set, let’s suppose that the following two points ended up being our training set, taken from the data shown above.
Furthermore, suppose that the perceptron separates the classes in the following manner.
Now the remaining points in the data set for validation or testing are the following, with the partition from training shown again as the same black line.
Note that the test points are now falling on opposite sides of the line, so that the perceptron will fail on classifying both of those data points, because it did not select the best partition during training.
Perceptron is guaranteed to have zero-error when trained with a linearly separable dataset. It outputs a hyperplane that perfectly separates your training samples. But, this doesn't mean that you'll perfectly classify the validation set. Because the perceptron didn't see those samples, it's probable that it picked a bad decision boundary (among the possibly infinite choices), even if it perfectly works with the training set. And, I agree with @Lucas's comment that real-life datasets don't possess linear separability in general.