Lower Bounds on Identification Criteria for Perceptron-like Learning Rules

We investigate the computational complexity of identifying neural weights
using Perceptron-like learning rules. These are understood as instructions
to change weights by a fixed amount after occurrence of an error. We are
considering worst-case bounds on the number of correction steps when the
training examples are taken from Boolean functions computable by McCulloch-Pitts
neurons. In order to avoid known exponential lower bounds for exact identification
we define and analyze three criteria that do not require that the learning
process generates weights that precisely represent the target function:
PAC identification, order identification, and sign identification. Our
results show that Perceptron-like learning rules cannot satisfy any of
these criteria when the number of correction steps is to be bounded by
a polynomial. This indicates that even by considerably lowering one's demands
one cannot prevent Perceptron-like rules from being computationally infeasible.