A Lower Bound on the Number of Corrections Required for Convergence of the Single Threshold Gate Adaptive Procedure

The adaptive single threshold gate realization procedure, originally proposed by Rosenblatt, has been rather extensively studied, and several upper bounds on the number of corrections required for its convergence have been derived. In this note a lower bound on the number of required corrections is determnined, and shown to differ from the upper bound by a factor of about n² where n is the number of binary variables. This new bound then implies the existence of classes of linearly separable functions for which the number of required corrections increases exponentially with n.