DEVIATION THEOREMS FOR PFAFFIAN SIGMOIDS

D. Yu. Grigoriev

Abstract. By a Pfaffian sigmoid with a depth d we mean a circuit with d layers in which rational operations are admitted at each layer, and to jump to the next layer one solves an ordinary differential equation of the type v′ = p(v) where p is a polynomial with the coefficients being the functions computed at the previous layers of the sigmoid. Thus, Pfaffian sigmoid computes Pfaffian functions (in the sense of A. Khovanskii). The deviation theorem is proved which states that for a real function 0 ≢ f computed by a Pfaffian sigmoid with a depth (or parallel complexity) d there exists an integer n such that the inequalities (exp (⋯ ( exp (|x|^{n}) ⋯)^{−1} ≤ |f(x)| ≤ exp (⋯ ( exp (|x|^{n}) ⋯) hold for all |x| ≥ x_{0} for a certain x_{0}, where the iteration of the exponential function is taken d times. One can treat the deviation theorem as an analogue of the Liouvillean theorem (on algebraic numbers) for Pfaffian functions.

Introduction

Under Pfaffian sigmoid (cf. [MSS], [G] ) with a depth d we understand a computational circuit having d layers such that at each layer the rational operations are admitted and for a jump to (i + 1)-th layer, computing a function w_{i+1} : ℝ → ℝ at (i + 1)-th layer is admitted, being a solution of a differential equation of the first order w′_{i+1} = p(w_{i+1}) (cf. [Kh] ) where p is a polynomial with the coefficients computed at the previous layers of the sigmoid (see (1) and the section 1 for the exact definitions). In particular, a jump could be made by taking exp or log of a function computed at previous layers, this kind of Pfaffian sigmoids are called elementary and were considered in [G], where more generally the sigmoids were introduced in which for a jump to the next layer one can substitute a function from a previous layer into a solution of a linear ordinary differential equation with the polynomial coefficients, thus, into exp or log, in particular. Another particular case of elementary sigmoids are “standard” sigmoids (see [MSS] ) where the jump is made by applying the function (1 + exp(−x))^{−1}. So, a function computed at (i + 1)-th layer of a sigmoid introduced in [G], satisfies a linear ordinary differential equation with the coefficients from the previous layers 1, …, i. In the present paper the corresponding differential

Typeset by AMS-TEX

AMS subject classification: 68C25.

Key words and phrases: pfaffian sigmoid, deviation theorems, parallel complexity.

equation could be non-linear, but of the special form (see (1) below), providing that the computed functions are Pfaffian (see [Kh] ).

The main result (see the theorem in the section 1) states that two different functions f_{1}, f_{2} : ℝ → ℝ computed by a Pfaffian sigmoids with a depth (or parallel complexity) d cannot be too close to each other, namely (exp(⋯ (exp p(x) ⋯)))^{−1} ≤ |(f_{1} − f_{2})(x)| ≤ exp(⋯ (exp p(x))) for a suitable polynomial p ∈ ℝ[x] and for all x ≥ x_{0} for some x_{0} ∈ ℝ, where the number of iterations of the exponential function equals to d. This type of the results was called in [G] the deviation theorem where they were proved for the sigmoids introduced in [G] (cf. above). Also the deviation theorem could be treated as an analogue of Liouvillean theorem on the bound on the difference of two (different) algebraic numbers, for the functions computed by Pfaffian sigmoids. In particular, it gives a lower bound on the approximation of a function computed by a Pfaffian sigmoid by means of a rational function (see the corollary in the section 1). On the other hand, one could interpret the theorem and the corollary as lower bounds on the depth (so, parallel complexity) of a Pfaffian sigmoid, computing a function, provided that it has a rather good approximation by a “simple” (for example, rational) function.

The proof of the theorem is conducted by induction on the depth of a sigmoid. In the section 2 an upper bound on a function computed by a Pfaffian sigmoid is ascertained (see the lemma), in the section 3 a lower bound and thus the inductive step are proved.

1. \underline{Pfaffian sigmoids and differential fields}.

Denote the field P_{0} = ℝ(X), then by induction on i the field P_{i+1} is generated over P_{i} by all the functions w_{i+1}^{(j)} : ℝ → ℝ (maybe having a finite number of singularities) satisfying first-order nonlinear differential equations of the form

(w_{i+1}^{(j)})′ = q (w_{i+1}^{(j)})  (1)

where a polynomial q(Z) ∈ P_{i}[Z].

According to [Kh] any function f ∈ P_{i}, being Pfaffian, has a finite number of singularities and roots (for i = 1 see also [B] ). Hence for every two functions f_{1}, f_{2} ∈ P_{i}, f_{1} ≠ f_{2} the difference (f_{1} − f_{2})(x) is either positive or negative everywhere on an interval x ∈ [x_{0}, ∞) for a certain x_{0} ∈ ℝ, we write f_{1} ≻ f_{2} or f_{1} ≺ f_{2} respectively. By p_{1}, p_{2}, ⋯ ∈ ℝ[X] we’ll denote the polynomials with the positive leading coefficients. By exp^{(i)} = exp(⋯ (exp) ⋯) we denote the iteration of the exponential function i times. Obviously exp^{(i)}(p_{1}), (exp^{(i)}(p_{1}))^{−1} ∈ P_{i}. Now we are able to formulate the main result of the paper (cf. [G] ).

Theorem. For any function 0 ≢ f ∈ P_{i} there exists a polynomial p_{1} such that

(exp^{(i)} p_{1})^{−1} ≺ |f| ≺ exp^{(i)} p_{1}.

The theorem will be proved in the next two sections, now we indicate the connections with the sigmoids (cf. [MSS] ). Under a Pfaffian sigmoid with the depth d we understand a computations consisting of d layers such that a function w_{i+1}^{(j)} at (i+1)-th layer satisfies an equation (1) where the coefficients q_{ℓ}, 0 ≤ ℓ ≤ n of the polynomial q(Z) = ∑_{0≤ℓ≤n} q_{ℓ}Z^{ℓ} are the rational functions in the functions of the form w_{i}^{(j_{1})} computed at the previous (1, …, i) layers of the sigmoid (cf. [G] ). Thus, at each layer of the Pfaffian sigmoid the rational operations are admitted and the jump from the previous layer to the next one is done by solving an equation (1). Thus, inducion on i shows that a function w_{i+1}^{(j)} computed at (i + 1)-th layer of a Pfaffian sigmoid belongs to P_{i+1}.

In [G] the elementary sigmoids were considered where the function w_{i+1}^{(j)} was obtained as either w_{i+1}^{(j)} = exp(f_{1}/f_{2}) or w_{i+1}^{(j)} = log(f_{1}/f_{2}) where f_{1}, f_{2} were the polynomials in the functions of the form w_{i}^{(j_{1})} computed at the previous (1, …, i) layers of the elementary sigmoid. Evidently, an elementary sigmoid is a particular case of Pfaffian sigmoids. In its turn, so-called “standard” sigmoid where the jump from the previous layers to the next one is fulfilled by applying the gate function (1 + exp(−x))^{−1} ( [MSS] ) is a particular case of the elementary sigmoids.

An important question, how good one can approximate a function computed by a Pfaffian sigmoid by means of a rational function (cf. [G] ).

Corollary. If a function w_{d} ∈ P_{d} is computed by a Pfaffian sigmoid with a depth d then for any rational function r ∈ P_{0} holds |w_{d} − r| ≻ (exp^{(d)}(p_{2}))^{−1} for a suitable polynomial p_{2}, unless w_{d} = r.

2. \underline{Upper bound on Pfaffian function}.

We start proving the theorem by induction on i. The base of induction for P_{0} is obvious, let us proceed to the inductive step. In the present section we’ll prove the required upper bound on the function w_{i+1}^{(j)} (see (1)).

Assume by inductive hypothesis the coefficients q_{ℓ} ∈ P_{i}, q_{n} ≠ 0 of the polynomial q satisfy the following inequalities (exp^{(i)}(p_{2}))^{−1} ≺ |q_{ℓ}| ≺ exp^{(i)}(p_{2}), 0 ≤ ℓ ≤ n for an appropriate polynomial p_{2}.

If |w_{i+1}^{(j)}| ≺ 4(exp^{(i)}(p_{2}))^{2} is valid, the required upper bound is proved. Suppose the contrary. Then

\frac{1}{2}(exp^{(i)}(p_{2}))^{−1} ≺ |q_{n} + \frac{q_{n−1}}{w_{i+1}^{(j)}} + ⋯ + \frac{q_{0}}{(w_{i+1}^{(j)})^{n}} | = |\frac{(w_{i+1}^{(j)})′}{(w_{i+1}^{(j)})^{n}} | ≺ exp^{(i)}(p_{2}) + 1

If n = 0 then |w_{i+1}^{(j)}(x)| ≤ C_{0} + ∫_{x_{0}}^{x}(exp^{(i)}(p_{2}) + 1) ≺ exp^{(i)}(p_{3}(x)) for sufficiently large x ≻ x_{0} and suitable polynomial p_{3} and C_{0} ∈ ℝ. If n ≥ 2 then |(w_{i+1}^{(j)}(x))^{−n+1}| ≥ (n − 1) ∫_{x}^{∞} \frac{1}{2}(exp^{(i)}(p_{2}))^{−1} ≻ (exp^{(i)}(p_{4}(x)))^{−1} for sufficiently large x and a suitable polynomial p_{4}, therefore |w_{i+1}^{(j)}| ≺ (exp^{(i)}(p_{4})). Finally, if n = 1 then log |w_{i+1}^{(j)}(x)| ≤ C_{1} + ∫_{x_{0}}^{x}(exp^{(i)}(p_{2}) + 1) ≺ exp^{(i)}(p_{5}(x)) for sufficiently large x ≻ x_{0} and suitable polynomial p_{5} and C_{1} ∈ ℝ, therefore |w_{i+1}^{(j)}| ≺ exp^{(i+1)}(p_{6}) for a suitable polynomial p_{6}.

We summarize the proved upper bound in the following lemma (for i = 0 one can find its proof in [B] ).

Lemma. Assume the statement of the theorem is proved for P_{i} and w_{i+1}^{(j)} satisfies (1) where deg(q) = n. Then

a) if n = 0 or n ≥ 2 then |w_{i+1}^{(j)}| ≺ exp^{(i)}(p_{7})

b) if n = 1 then |w_{i+1}^{(j)}| ≺ exp^{(i+1)}(p_{7})

for an appropriate polynomial p_{7}.

Remark. For any polynomial h ∈ P_{i}[Y_{1}, …, Y_{m}] the similar upper bound as in the lemma |h(w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})})| ≺ exp^{(i+1)}(p_{8}) is valid where the functions w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})} satisfy similar to (1) equations, namely (w_{i+1}^{(j_{s})})′ = q^{(s)}(w_{i+1}^{(j_{s})}) where q^{(s)} ∈ P_{i}[Z], 1 ≤ s ≤ m. This is an upper bound on a function h(w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})}) ∈ P_{i+1} required in the theorem.

3. \underline{Lower bound on Pfaffian function}.

Now we proceed to proving a lower bound on |h(w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})})| required in the theorem. Firstly, we consider the case when w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})} are algebraically independent over P_{i}. Assume that the required lower bound is wrong, so |h(w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})})| ≺ (exp^{(i+1)}(p_{ℓ}))^{−1} for all the polynomials p_{ℓ}. Then we say that the function h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}) is small. Also we assume that m is the least possible with this property. Finally, without loss of generality one can assume that the polynomial h is irreducible over P_{i}.

As the derivative (h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}))′ ∈ P_{i+1} is a Pfaffian function [Kh], it should

be also small. One can represent (h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}))′ = ∑_{1≤s≤m} _{\frac{∂h}{∂w_{i+1}^{(js)}}} · q^{(s)}(w_{i+1}^{(j_{s})}) =

g(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}) for a certain polynomial g ∈ P_{i}[Y_{1}, ⋯, Y_{m}].

If h ∤ g in the ring P_{i}[Y_{1}, ⋯, Y_{m}] then there exist polynomials h_{1}, g_{1} ∈ P_{i}[Y_{1}, ⋯, Y_{m}] such that 0 ≢ h h_{1} + gg_{1} ∈ P_{i}[Y_{1}, ⋯, Y_{m−1}] since h is irreducible. But then the function (hh_{1} + gg_{1})(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m−1})}) is small, applying the remark at the end of the section 2 to the polynomials h_{1}, g_{1}, that contradicts to the minimality of the choice of m.

Now suppose that g = hg_{0} where g_{0} ∈ P_{i}[Y_{1}, ⋯, Y_{m}]. Consider any 1 ≤ s ≤ m for which deg_{Z}(q^{(s)}) ≤ 1, then deg_{w_{i+1}^{(js)}} (_{\frac{∂h}{∂w_{i+1}^{(js)}}} q^{(s)}(w_{i+1}^{(j_{s})})) ≤ deg_{w_{i+1}^{(js)}}(h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})) and as deg_{w_{i+1}^{(js)}} (_{\frac{∂h}{∂w_{i+1}^{(j_{ℓ})}}} q^{(ℓ)}(w_{i+1}^{(j_{ℓ})})) ≤ deg_{w_{i+1}^{(js)}}(h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})) for every ℓ ≠ s, hence w_{i+1}^{(j_{s})} does not occur in the polynomial g_{0}(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}). If for some 1 ≤ s ≤ m deg_{Z}(q^{(s)}) ≥ 2 then lemma implies that |w_{i+1}^{(j_{s})}| ≺ exp^{(i)}(p_{9}) for an appropriate polynomial p_{9}. Therefore |g_{0}(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})| ≺ exp^{(i)}(p_{10}) for a certain p_{10}. Thus, |\frac{(h(w_{i+1}^{(j_{1})},··· ,w_{i+1}^{(jm)}))′}{h(w_{i+1}^{(j_{1})},··· ,w_{i+1}^{(jm)})} | ≺ exp^{(i)}(p_{10}), hence | log |h(w_{i+1}^{(j_{1})}), ⋯, w_{i+1}^{(j_{m})}| | ≺ exp^{(i)}(p_{11}) and |h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})| ≻ (exp^{(i+1)}(p_{11}))^{−1}. This contradicts to the assumption that h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}) is small and proves the required in the theorem lower bound in the case when w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})} are algebraically independent over P_{i}.

In the general case choose some transcendental over P_{i} basis (let it be w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{s})} without loss of generality) among w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}. Then there exists a polynomial t(Z) =

∑_{0≤ℓ≤K} t^{(ℓ)}Z^{ℓ} ∈ P_{i}[w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{s})}][Z] where the coefficients t^{(ℓ)} ∈ P_{i}[w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{s})}], 0 ≤

ℓ ≤ K and t^{(0)} ≢ 0, such that t(h(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})) ≡ 0. Since we have proved that |t^{(0)}| ≻ (exp^{(i+1)}(p_{12}))^{−1} and by lemma and remark after it |t^{(ℓ)}| ≺ (exp^{(i+1)}(p_{12})), 0 ≤ ℓ ≤ K for a certain p_{12}, we obtain that |h(w_{i+1}^{(j_{1})}, …, w_{i+1}^{(j_{m})})| ≻ \frac{1}{2}(exp^{(i+1)}(p_{12}))^{−2}.

This completes the proof of the inductive step in the proof of the theorem (see the beginning of the section 2) because any element in P_{i+1} can be represented as a quotient h^{(1)}(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})})/h^{(2)}(w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})}) for some elements w_{i+1}^{(j_{1})}, ⋯, w_{i+1}^{(j_{m})} ∈ P_{i+1} satisfying the equations of the kind (1) (w_{i+1}^{(j_{s})})′ = q^{(s)}(w_{i+1}^{(j_{s})}), 1 ≤ s ≤ m and for some polynomials h^{(1)}, h^{(2)} ∈ P_{i}[Y_{1}, ⋯, Y_{m}]. The theorem is proved.

BIBLIOGRAPHY

[B] Bellman, R., Stability theory of differential equations. McGraw-Hill Book Co., 1953..

[G] Grigoriev, D., Deviation theorems for solutions of linear ordinary differential equations and applications to lower bounds on parallel complexity of sigmoids, to appear.

[Kh] Khovanskii, A., Fewnomials, Transl. Math. Monogr. AMS, 88 (1991).

[MSS] Maass, W., Schnitger, G., Sontag, E., On the computational power of sigmoid versus boolean threshold circuits, Proc. 32 FOCS, IEEE, (1991), pp. 767–776.

Departments of Computer Science and Mathematics Penn State University State College, PA 16802 USA

On leave from Mathematical Institute Fontanka 27 St. Petersburg 191011 RUSSIA