Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids

D. Yu. Grigoriev

Algebra i analiz, Tome 6 (1994) no. 1, pp. 110-126.

Résumé

By a sigmoid of depth $d$ we mean a computational circuit with $d$ layers in which rational operations are admitted at each layer, and to jump to the next layer the substitution of a function computed at the previous layer in an arbitrary real solution of a linear ordinary differential equation with polynomial coefficients is admitted. Sigmoids arise as a computational model for neural networks. We prove the deviation theorem stating that for a (real) function $f$, $f\not\equiv 0$, computed by a sigmoid of depth (or parallel complexity) $d$ there exists $c>0$ and an integer $n$ such that the inequalities. $(\exp(\dots(\exp(c|x|^n))\dots))^{-1}\leq|f(x)|\leq\exp(\dots(\exp(c|x|^n))\dots)$ hold everywhere on the real line except for a set of finite measure, where the iteration of the exponential function is taken $d$ times. One can treat the deviation theorem as an analog of the Liouville theorem (on the bound for the difference of algebraic numbers) for solutions of ordinary differential equations. Also we estimate the number of zeros of $f$ in an interval.

Détail

Keywords: Sigmoid, parallel complexity, deviation theorems, bounds for Wronskian.