LEARNING TIMES OF A PERCEPTRON THAT LEARNS FROM EXAMPLES

We calculate the distribution of learning times of the optimal stabili ty perceptron algorithm of Krauth and Mezard (1987) for the learning f rom noisy examples problem. In particular, we find that in the case of noiseless examples the average total number of learning steps scales with alpha(2), where alpha is the training set size, although the numb er of examples that must effectively be learned tends to zero as alpha (-1).