Computing Time Lower Bounds for Recurrent Sigmoidal Neural Networks

Part of Advances in Neural Information Processing Systems 14 (NIPS 2001)

Bibtex Metadata Paper


M. Schmitt


Recurrent neural networks of analog units are computers for real(cid:173) valued functions. We study the time complexity of real computa(cid:173) tion in general recurrent neural networks. These have sigmoidal, linear, and product units of unlimited order as nodes and no re(cid:173) strictions on the weights. For networks operating in discrete time, we exhibit a family of functions with arbitrarily high complexity, and we derive almost tight bounds on the time required to compute these functions. Thus, evidence is given of the computational lim(cid:173) itations that time-bounded analog recurrent neural networks are subject to.