Average-Case Complexity of Learning Polynomials

Frank Stephan∗
Mathematisches Institut
Universität Heidelberg
Im Neuenheimer Feld 294
69120 Heidelberg, Germany
fstephan@math.uni-heidelberg.de

Abstract

proved within the PAC model are usually worst-casebounds.

The present paper deals with the averagecase complexity of various algorithms for learning univariate polynomials. For this purpose
an appropriate framework is introduced. Based on it, the learnability of univariate polynomials evaluated over the natural numbers andof univariate polynomials defined over finite
fields is analyzed.

Since experimental studies have shown quite often alarge gap between the worst-case bounds proved and theactual runtime observed, several authors advocated toanalyze the average-case behavior of learning algorithms(cf., e.g., [7, 10, 12, 14, 15, 16, 17, 18]). We continue
along this line of research.

Our results are manifold. In the first case,convergence is measured not relative to the degree of a polynomial but with respect to a measure that takes the degree and the size of thecoefficients into account. Then standard interpolation is proved not to be the best possible
algorithm with respect to the average numberof examples needed.
In general, polynomials over finite fields are
not uniquely specified by their input-outputbehavior. Thus, as a new form of data representation the remainders modulo other polynomials is proposed and the expected example
complexity is analyzed for a rather rich classof probability distributions.

1

Introduction

Learning concepts efficiently has attracted considerable attention during the last decade. However, within
the field of inductive inference traditionally the mainemphasis has been put on analyzing the update time,i.e., the effort to compute a single new hypothesis. On
the other hand, starting with Valiant’s [21] pioneering paper, the total amount of examples and/or timeneeded to solve a given learning problem has become
quite popular. Nevertheless, the complexity bounds∗

Thomas Zeugmann†
Institut für Theoretische Informatik
Medizinische Universität Lübeck
Wallstraße 40
23560 Lübeck, Germany
thomas@tcs.mu-luebeck.de

This author was supported by the Deutsche Forschungsgemeinschaft (DFG) under grant no. Ste 967/1–1.
†
Supported by the Grant-in-Aid for Scientific Researchin Fundamental Areas from the Japanese Ministry of Education, Science, Sports, and Culture under grant no. 10558047.

Within this paper we deal with the problem to learn
efficiently univariate integer valued polynomials as wellas univariate polynomials over finite fields from two different sources of information. The underlying model isGold [9]-style learning in the limit, i.e., the learner has
to produce a sequence of hypotheses that stabilizes to acorrect and finite description of the target polynomial.
We always choose the target class of all relevant polynomials as hypothesis space.
Classically, the source of information are incrementally growing sequences of pairs argument–value. Angluin and Smith [2] describe two methods for learning
integer valued polynomials in this setting. The first
method is identification by enumeration (cf. Gold [9]).
Here, a canonical enumeration of all target polynomials
is assumed and the learner searches on every input for
the first polynomial in the enumeration that matches
the data. Clearly, it then converges to the first enumerated polynomial that equals the target.
The second method is learning by interpolation, i.e.,
the learner always computes the interpolation polynomial from the data given. Polynomial interpolation
is a widely studied and well understood problem (cf.,e.g., Bini and Pan [4]). So in the general case, there
are algorithms which synthesize a formula for a desired
polynomial over the rational or real numbers from n+1
pairs (x, g(x)) where g is the desired polynomial andn is its degree.
We aim to compare these methods with respect totheir average-case example and time complexity. Partof our motivation is a result obtained by Gold [9] andgeneralized by Jantke and Beick [13] stating that identification by enumeration is an optimally data efficientmethod. Here, the data efficiency of a learner is measured by the quantity of data it needs to converge to acorrect hypothesis. If L1 and L2 are two learning algorithms, then L1 is as data efficient as L2 iff, for every
admissible information presentation and every target,
L1 does not need more data than L2 to converge. L1is strictly more data efficient than L2 if L1 is as data
efficient as L2 but there is a target and a data presentation for it such that L1 needs strictly less data than L2
until convergence. Finally, a learning method is called
optimally data efficient if there is no other learner thatis strictly more data efficient.
While these investigations have been undertaken in
a setting where learning is required from every information presentation, our goal is to analyze the averagecase complexity of these two methods. We define ouraverage-case model by specifying a rather rich class ofprobability distributions over the natural numbers (cf.
Section 2). Then, every datum x will be drawn independently at random with a certain probability. Thus,
one obtains randomly generated sequences ((x, g(x)))
and the learner is fed incrementally growing initial segments of the sequence generated.
Then we consider the problem of learning polynomials over a finite field. For seeing the main two differences, let us assume that we have to learn polynomials
defined over the finite field IF2 .
(1) Now, the polynomials considered are defined only
for two inputs, i.e., input 0 and input 1 . Therefore
they are not fully described by the mapping x → g(x)for x ∈ {0, 1} and one has to look for other ways todescribe them. The way chosen in the present paper is
to supply the data as a random sequence of pairs (a, b)
where b is the remainder polynomial obtained when
the target polynomial g is divided by polynomial a .
This generalization reintroduces a mode to describe thewhole polynomial. We refer to this model as to learningfrom remainder sequences.
(2) In the standard case, all data fed to the learnerare of the form (x, g(x)) and have the same information
content. Thus, n + 1 different data items — whatever
they are — describe exactly the target polynomial gwhile n do not do it. This beautiful property is lost in
the model considered here, i.e., when learning from remainder sequences. Taking for example a product g1 g2 ;then all pairs (a, b) where a is dividing g1 do not contribute any knowledge about g2 , but there might be 2ndivisors for some polynomial g1 of degree n2 — for example obtained by multiplying n coprime polynomialsof length n . So the degree is not an upper bound on
the number of data-items needed to learn a polynomial.
On the other hand, a single data-item can give a fulldescription of the polynomial: if deg(a) > n then theb in the pair (a, b) is already the correct polynomial
wanted.
For defining our average-case model, we have to introduce a class of probability distributions over the set
IFq [x] of all relevant polynomials (where IFq is a finite
field of order q ). Clearly, this class should be chosen in-

dependently of the target polynomial. That is, we first
fix the class of admissible probability distributions D
and then analyze the expected complexity of learningfrom remainder sequences drawn with respect to some
distribution from the class D .
For defining D , all polynomials from IFq [x] shouldhave a non-zero probability except the zero polynomial.
Since IFq [x] is infinite, the limit superior (as n tends toinfinite) of the probability to show up for a polynomialof degree n has to be zero. That is, high degree polynomials have low probability and the higher the degree
the smaller is the relevant probability. On the other
hand, there is no reasonable cause to assume different
probabilities for polynomials of the same degree. Thus,
the distributions in D considered in the present work
are all of a quasi uniform type.
The complexity of our learning algorithms is analyzed with respect to two average measures: The example complexity is the average number of examples usedby the learning algorithm until it comes up with thecorrect hypothesis. The time complexity is the average
number of computation steps until the correct polynomial g is found. Naturally, the example complexity isalso a lower bound for the time complexity.
Next, we introduce some notions and notations usedwithin the present paper.
By IN = {0, 1, 2, . . .} we denote the set of all natural
numbers, and we set IN+ = IN \ {0} . The symbol ZZ
is used for the set of all integers. Any finite field isdenoted by IF . If IF is a finite field, we write p for its
characteristic and q for its order. Note that p is always
a prime and q = p` for some ` ∈ IN+ . Therefore, we
usually write IFq for the, up to isomorphism, uniquefield of order q . For more information concerning finite
fields the reader is referred to Berlekamp [3].
If g is any polynomial; then we use deg(g) to denote its degree.
Finally, we recall the following important proposition from probability theory that will be used frequently.
Proposition 1 (Feller [8]). Assume that there isa source of examples such that every example has withprobability r > 0 a certain property u . Then the average number of examples to be drawn until some example
satisfying u comes up is just 1r . The average numberof examples necessary to draw n such examples is nr .
This paper is organized as follows. In Section 2
we present a new algorithm for learning integer valued
polynomials from sequences argument-value and analyze its average-case complexity with respect to a rather
large class of probability distributions. The averagecase complexity of learning polynomials over finite fields
from remainder sequences is studied in Section 3. Finally, we outline conclusions.

2

Learning Polynomials on Natural
Numbers

Throughout this section, the target class is the setof all integer-valued polynomials. For learning a target
polynomial g , the source of information given to thelearner are pairs (x, g(x)) , where x ∈ IN . Next, wehave to specify the class of admissible probability distributions D over IN . That is, a datum x will then be
drawn with probability p({x}) , and the learner is fed(x, g(x)) . For defining a rather rich class of probability
distributions, we make only the following two assumptions about p . First, p({x}) > 0 for all x ∈ IN , since
we have no reason to distinguish any x ∈ IN by assigning probability 0 to it. Second, p({x}) ≥ p({y}) for
all x, y ∈ IN with x ≤ y . The motivation for the second assumption is as follows. Since IN is infinite, thelimit superior of p({x}) (as x tends to infinite) has
to be zero. That means, large numbers must have low
probability and the larger x is the lower is the relevant
probability.
As we shall see later, it will be more convenient todeal with the probability that some datum from theset {x, x + 1, x + 2, . . .} has been drawn rather than aparticular one. Therefore, we specify the class D via
functions f defined by f (x) = p({x, x + 1, . . .}) , i.e.,f describes the probability to draw some datum from{x, x + 1, x + 2, . . .} . Now, one easily verifies that f isdecreasing, and the following properties are fulfilled:

Gold [9] as well as Jantke and Beick [13] showed thatlearning by enumeration is optimally data-efficient. The
same is true also for interpolation.
Proposition 2.
efficient.

Interpolation is optimally data-

Proof. Interpolation returns to any n + 1 different
data-items a polynomial of degree n and keeps that
hypothesis until some data comes up showing that it
is incorrect. Assume by way of contradiction that someother algorithm M would be strictly more data-efficientthan interpolation. Then M learns some polynomial g
before it is interpolated, that is, M outputs a correct
hypothesis for g on some data (x0 , y0 ), (x1 , y1 ), . . . ,(xn , yn ) although deg(g) > n . As a consequence, M
does not identify the polynomial g 0 interpolating thissequence from these n + 1 data-items, which contradicts the fact that M is at least as data-efficient asinterpolation.
So alternatives to interpolation are more incomparable to it than better on all possible polynomials anddata-sequences. The main axiom of interpolation is thatthe easiest way to describe a set of data is to take thepolynomial of least degree interpolating it. That is, interpolation is based on the assumption that a data-itemof the form
(10000, 100020001)
is more likely to describe the polynomial
g(x) = 100020001(1) f (0) = 1 ,(2)than the polynomial

lim f (x) = 0 ,h(x) = x2 + 2x + 1 ;x→∞(3) f (x) > 0 for all x ∈ IN , and(4) f (x) − f (x + 1) ≥ f (x + 1) − f (x + 2) .
So f is very parallel to the parameter function fused in the next section. D is now the set of all probability distributions generated by a decreasing function
f satisfying (1) through (4) above.
Interpolation is the best known method for learning
polynomials. It returns to all data-items a hypothesis
in polynomial time and its average-case complexity is a1
bit below f (0)·f (1)·...·f(n) (cf. [20]):• There are polynomial time algorithms to computea formula for a polynomial g of least degree interpolating given data (x0 , y0 ), (x1 , y1 ), (x2 , y2 ), . . . ,(xn , yn ) .
• It needs n + 1 different examples for identifying apolynomial of degree n ; the average example complexity is just the number of draws necessary until n + 1 different values are obtained. An upperbound of the expected example complexity of learning polynomials by interpolation is then1.
f (0) · f (1) · . . . · f (n)so the size of the coefficients is totally ignored. The
subsequent model therefore tries to find for given datarather a polynomial having small absolute values of thecoefficients rather than being of small degree. This approach leads us to a definition of the size of a polynomialthat takes into account not only the degree but also theabsolute value of the coefficients. Integer valued polynomials may have rational coefficients, for example theclearly integer-valued polynomial
x → 0 + 1 + ... + x
has the formula

1 2 1
x + x.
2
2
Every integer-valued polynomial of degree k is of the
form
 
 
 
x
x
x
g(x) = a0+ a1+ . . . + ak,
01k
where all ai ∈ ZZ , ak 6= 0 and xx · (x − 1) · . . . · (x − h + 1)=h
1 · 2 · ... · his the binomial coefficient for x and h . Note that x
= 0 for all x < h .
hFor example,
1
1g(x) = x2 + x
2
2
has then the form   xxg(x) =+,
1
2i.e., a0 = 0 , a1 = a2 = 1 .
Using this general form, a natural definition of thesize of a polynomial g issize(g) = max{1, deg(g), |a0 |, |a1 |, . . . , |ak |}.
Here deg(g) ≤ k , and equality holds in the case thatak 6= 0 . The next theorem shows that — with highprobability — every polynomial of size n can be learned
within polynomial time from logarithmically many examples.
Theorem 3. Let g be any target polynomial whose
size is unknown to the learner. Then, an optimal algorithm learning g from data-items drawn at randomwith respect to f needs(1) at least (f (size(g)))−1 and(2) at most (f (5 · (size(g))2 ))−1 many examples untilconvergence.
Proof. For proving
 Assertion (1), consider the twopolynomials x → nx and x → − nx . They have sizen and do not differ at the places 0, 1 . . . , n − 1 . Thus,
the learner has to see some pair (x, g(x)) with x ≥ n
to make up its mind. So, the expected number to draw
1
examples until such a pair comes up is f (size(g)).
For proving Assertion (2), consider the following algorithm:
Let (x, g(x)) be the data-item with the largest
x seen so far.
Let n be the largest natural number such that
5n2 ≤ x .
Initialize a0 , a1 , . . . , an with the value −n .
For m = n, n − 1, . . . , 0 increment
am untilxeither am = n or g 0 (x) + m> g(x) for thepolynomial g 0 defined by the current values of
the coefficients a0 , a1 , . . . , an .
Output g(x) = a0 + a1 x1 + . . . + an nx .
It is easy to see, that this algorithm converges. Since
each am is increased at most 2n times and since there
are only n variables, the whole algorithm needs to com-2xpute the current values of g 0 (x) + m
at most 2ntimes.
Next, it is shown that the output is correct under
the assumption that size(g) ≤ n .
Assume now by way of contradiction, that the algorithm terminates with some g 00 such that g 00 6= g . Let

b0 , b1 , . . . , bn be the coefficients of g and a0 , a1 , . . . , anthose of g 00 . There is a largest m such that bm 6= am .
If am < bm , then the algorithm stops at the m th loop before
incrementing
am to


 bm , in particu
xxlar, −n x0 − n x1 − . . . − n m−1+ (am + 1) m
+


x
x
am+1 m+1 + . . . + an n > g(x) . This implies byx
ak = bk for k > m that −n x0 −n x1 −. . .−n m−1
+




x
x
(am + 1) m
> b0 x0 + b1 x1 + . . . + bm−1 m−1+xbm m . This assumption contradicts to the fact thatthe am + 1 ≤ bm and −n ≤ bk for all k . So this casedoes not occur.

Otherwise
am > bm . This impliesthat −n x0  −xx
n x1 − . . . − n m−1+ (bm + 1) m
≤ b0 x0 + b1 x1 +xx
. . . + bm−1 m−1 + bm m since otherwise am could
never been incremented
 to a valuex greater than xbm .
x
So one gets that m≤ (b0 + n) 0 + (b1 + n)x 1 +x. . . + (bm−1 + n) m−1. Using bk ≤ n , m ≤ 5 and



x
x
x
x
that, for k < 5 , k < 12 k+1
one gets that m
≤


x
x
2n · (21−m + 22−m + . . . + 20 ) m−1≤ 4n · m−1. In
particular x + 1 − m ≤ 4nm which contradicts therequirements m ≤ n and x ≥ 5n2 from the choice ofm and n . Thus, am > bm is impossible either.
So, it follows from the case-distinction that g 00 = g
whenever the parameter n is an upper bound for thesize of g . In particular the example complexity of thealgorithm is (f (5 · (size(g))2 ))−1 .
Before discussing further consequences of our Theorem 3, we shortly illustrate the learner described in the
proof above.
Example 4. Let g with g(x) = 1 for all x be
the target polynomial to be learned by the algorithm
given in the proof above. Thus, size(g) = 1 and wetherefore consider the data item (5, 1) which has thesmallest possible x .
Now, first the algorithm computes n = 1 , and therefore g10 (x) = −x − 1 . During the first loop, i.e., m = 1 ,only the coefficient a1 is possibly changed while the actual a0 = −1 remains unchanged.
Since a1 = −1 6= 1 = n , the algorithm then tests−5 − 1 + 5 > 1 which is false. Therefore, g20 (x) = −1 .
Since 0 6= 1 , it tests −1 + 5 > 1 which is true. Thisfinishes the loop for a1 with a1 = 0 , and the second
loop, i.e., m = 0 , is started with g20 (x) = −1 . Now,
the condition to be checked is −1 = 1 or −1 + 1 > 1
which returns false. Thus, g30 (x) = 0 . Since 0 6= 1 , ittests 0 + 1 > 1 which is false. Finally, g40 (x) = 1 , andthe algorithm terminates, since 1 = 1 . Hence, it hascorrectly learned the target g .
Note that the time-complexity of the algorithm presented in the proof of Theorem 3 could be improved bysearching the am via interval search; the main reason
for giving the algorithm as above was to get an easier verification. The following example gives concretebounds for the case that the distribution is given by
f (n) =

1.
log(n + 2)

Example 5. There is an algorithm which learns
polynomials with example complexity
log(2 + 5 · (size(g))2 )where the distribution is given by

1
f (n) = log(n+2).

Next, we compare the latter result to learning by interpolation. Let n > 1 ; there are (2n + 1) · (2n + 1)nmany polynomials having size at most n . Among thesepolynomials, there are 2n · (2n + 1)n many polynomials
that have degree n . For these polynomials of degree n
the standard interpolation procedure requires n+1 different data-items. On the other hand, for the distribu1
tion described by f (n) = log(n+2), our algorithm needs
for all polynomials of size at most n only log(5n + 2)2
many examples. So the example complexity of the algorithm presented above is for the great majority ofthe polynomials of size at most n better than standard
interpolation when measured with respect to the dis1
and taking thetribution described by f (n) = log(n+2)
size instead of the degree as a key parameter.
On the other hand, interpolation beats this algorithm if the underlying probability distribution is given
by f (n) = 2−n . Then the example complexity to get
all values g(0), g(1), . . . , g(n) is 2n(n+1)/2 while the example complexity to get one value g(x) with x ≥ 5n2
2
is 25n .
Next, we turn our attention to the problem that analyzing only the expected number of examples needed
until convergence is not so interesting. As often criticized by statisticians, expected values alone are not so
informative. Thus, we are interested in knowing on how
often the example complexity exceeds the average substantially.
For that purpose, we first note that the learner presented in Theorem 3 has two important properties, i.e.,
it is conservative and set-driven. A learner is set-driven,
if its output depends only on the range of its input (cf.
Wexler and Culicover [22]), while conservative learners
maintain their actual hypotheses at least as long as they
have not seen data contradicting them (cf. Angluin [1]).
Now, let X be a random variable standing for the example complexity of the algorithm in the proof of Theorem 3, and let E[X] denote the expectation of X .
Then, using a result by Rossmanith and Zeugmann [19],we directly obtain the following corollary.
Corollary 6.
t ∈ IN .

Pr(X ≥ 2tE[X]) ≤ 2−t for all

Consequently, our learner additionally possesses exponentially shrinking tail bounds for the example complexity. We can therefore transform the above algorithm
into one that probably exactly identifies every target

polynomial of size at most n provided a computable
upper bound fˆ for f is available to the learner. Probably exact learning is defined in the same way as PAC
learning, except that the hypothesis output has to becorrect rather than approximately correct. Additionally, it assumes a bit knowledge concerning the underlying distributions.
Theorem 7. Let n ∈ IN , and let fˆ be a computable
upper bound for f . Then there is an algorithm probably
exactly learning every target polynomial of size at mostn for every distribution f ∈ D with f (x) ≤ fˆ(x) for
all x ∈ IN using (2fˆ(5n2 ))−1 log 1δ many examples.
Proof. The desired learner takes any δ ∈ (0, 1) asadditional input. Now, using the algorithm defined in
the proof of Theorem 3, the learner performs log(1/δ)
many rounds.
In each round it requests (2fˆ(5n2 ))−1 many examples. During the first round, it computes a hypothesis
by using the learner from Theorem 3. By Corollary 6,
this hypothesis is already correct with probability atleast 1/2 . In the remaining rounds, a new hypothesis
is only computed if a data item (x, g(x)) is received
such that x > y for all y in the data items (y, g(y))
received so far. The last hypothesis computed is thenoutput.
Therefore, the probability that none of the computed
hypotheses is correct can be bounded by δ , i.e., withprobability 1 − δ the learner outputs a correct hypothesis after having processed (2fˆ(5n2 ))−1 log(1/δ) many
examples. Since fˆ is an upper bound for f , the theorem follows.
We finish this section by comparing the latter result
to PAC learning. Clearly, the PAC model is distribution
free, and therefore, the best one can hope for is to getbetter bounds on the number of examples needed forspecial classes of distributions. This is indeed the caseas we shall see.
Assuming n to be again a bound on the size of all
target polynomials, one can easily determine the VC
dimension of the class of all these polynomials to be n .
Thus, a PAC learner needs at least O( 1ε log 1δ + nε ) many
examples. Compared to the bound in Theorem 7, this1bound is worse provided fˆ(n) < √n+1.
Further generalizations are possible by removing theparameter n for the upper bound of the size. For the
PAC model, this has been shown in [11]. Their technique can be generalized to the setting considered in
Theorem 7.

3

Learning from Remainder Sequences

Next, we turn our attention to learning univariate
polynomials over finite fields. As already mentioned inthe introduction, now the situation is slightly different
from that studied in the previous subsection, since evencomplete sequences of pairs argument-value do not provide enough information to learn the target polynomial.
Therefore, we propose a new source of information,i.e., learning from remainder sequences. That is, now
the learner has access to pairs (a, b) , where a is any
polynomial and b is the remainder of the target polynomial when divided by a . Again, we require the learnerto infer the target in the limit from any such sequence.
This information shares some nice properties withthe standard source of information given by sequencesof argument-value. First, it is also easy to compute(only a bit more complicated than polynomial evaluation). Second, it contains enough information to learn
the target polynomial. Third, though one can learn thetarget from this information, learning does not become
easier in the sense that learning in the limit could be
replaced by finite learning. Here, finite learning meansthat the learner can decide whether or not it has alreadysuccessfully finished its learning task (cf. Gold [9]).
In some sense, learning even becomes harder. As
we have already said, in the standard case it is always
sufficient to have n + 1 data items argument-value tolearn any polynomial of degree n . This nice property
is lost in our new model. Taking into considerationthat there are (q − 1)q m different polynomials in IFq [x]of degree precisely m , it is easy to see that it may
take exponentially many examples (in the degree n of
the target polynomial) until convergence. On the other
hand, a single data item is sufficient in the best-case (ifdeg(a) > deg(g) , where g is the target polynomial).
Consequently, in the new setting the best-case andworst-case are overly optimistic and pessimistic, respectively. Therefore, we study the average-case complexityof this learning task. This requires the introduction ofa class of probability distributions over the whole set
IFq [x] of polynomials. Since IFq [x] is infinite, there isno uniform distribution. We therefore consider a ratherrich class of quasi uniform distributions over IFq [x] defined as follows.
Definition 8. For every finite field IFq we define
the class D of quasi uniform distributions over IFq [x]to be the set of all probability distributions generated
by any decreasing function f satisfying(1) f (0) = 1 ,(2)

lim f (n) = 0 ,n→∞(3) f (n) 6= 0 for all n ≥ 1 , and(4) f (n) − f (n + 1) ≥ f (n + 1) − f (n + 2) .
The probability of a non-zero polynomial a is thenjust
1(f (deg(a)) − f (deg(a) + 1)) ·(q − 1) · q deg(a)Conditions (1) and (2) in Definition 8 are necessary
to obtain a probability distribution. For seeing this,note that there are precisely (q − 1) · q m many polynomials of degree m . Thus, the probability to draw somepolynomial a of degree d is (f (deg(a)) − f (deg(a) +1)) . Now, looking at the sequence (Sm )m∈IN of partial
sums, we get that
Sm =

m
X

(f (d) − f (d + 1)) = f (0) − f (d + 1) ,d=0

and hence limm→∞ Sm = f (0) = 1 .
Furthermore, Condition (3) ensures that all polynomials have a non-zero probability. Finally, Condition(4) formalizes the requirement that all polynomials ofdegree n + 1 have a lower probability than those ofdegree n .
First, we establish lower and upper bounds for learning from remainder sequences. In the following, whenever talking about learning algorithms for polynomials
from IFq [x] , it is assumed that all these algorithms infer
to whole target class IFq [x] .
Theorem 9. Let g ∈ IFq be any target polynomialof degree n ( where n is unknown to the learner ) .
Then we have:(1) Every algorithm learning the target polynomial gfrom remainder sequences drawn at random withrespect to f needs at least(f (logq (n) − 2 logq logq (n)))−1
many examples until convergence.
(2) There exists an algorithm learning g from remainder sequences drawn at random with respect to fthat needs at most (f (n + 1))−1 many examples
until convergence.
Proof. For proving Assertion (1), choose the uniquem such that mq m+1 < n ≤ (m + 1)q m+2 . Let g1 be
the product of all polynomials of degree up to m . There
are precisely (q − 1) · q d many polynomials of degree d ;thus the degree of g1 can be upper bounded bym · (q − 1) ·mXq d ≤ m · q m+1 .

d=1

Let g2 be any polynomial of degree n − deg(g1 ) .
Now the lower bound is obtained by analyzing the expected number of examples necessary for learning thepolynomial g = g1 g2 . Any polynomial of degree up
to m is a divisor of g1 . Therefore, no data (a, b)with deg(a) ≤ m gives any information on the particular form of g2 . Hence, the learner cannot succeed before seeing at least one data item (a, b) withdeg(a) > m . Such a polynomial a occurs with probability at most f (m + 1) and therefore, the example
complexity is at least (f (m + 1))−1 which is an upperbound for (f (logq (n) − 2 logq logq (n)))−1 .

For proving Assertion (2) consider the learning algorithm that always conjectures b for the pair (a, b)
seen so far where a has the highest degree. Note thatb = p whenever deg(a) > deg(p) . Since such an a
has to be drawn up eventually, the algorithm converges.
It remains to show the example bound given by thisalgorithm matches the bound given in (2). The eventthat deg(a) > n has probability f (n + 1) and thus,
by Proposition 1, the expected number of examples is(f (n + 1))−1 until such a polynomial a shows up.
Next, we discuss the bounds obtained in Theorem 9
by looking at very slowly and very rapidly decreasing
functions f . For the former, let f (2n ) = 12 f (n) andrequire f to be uniformly decreasing for all arguments
inbetween two consecutive powers of 2 . That is, f (0) =1 by Condition (1) in Definition 8, f (1) = 1/2 , f (2) =1/4 f (3) = 3/16 , f (4) = 1/8 , f (5) = 15/128 , f (6) =14/128 , f (7) = 13/128 , f (8) = 3/32 , . . . , f (16) =1/16 , . . . , and so on. Now, it is easy to see that thedifference between the bounds given in Theorem 9 is
only a constant factor.
But for distributions given by other functions f likef (n) = q −n the gap is large. Now, the upper boundq n+1
and the lower boundq log(n)−2 log log(n) = n · (log(n))−2differ exponentially.
Consequently, while the gap between lower and upper bound in Theorem 9 can be large for some distribution in D , one can expect better bounds for particular distributions. So the next two results improve thebounds for the distribution given by f (n) = q −n .
Theorem 10. Let g ∈ IFq [x] be any target polynomial of degree n ( n again unknown to the learner ) .
Then every algorithm learning g from remainder sequences drawn at random with respect to the distribution
generated by f (n) = q −n has at least example complexn2
ity q −4 · log(n)for sufficiently large n .
Proof. (Sketch) This lower bound is obtained byadapting the previous proof and by exploiting special
knowledge on the distribution. Let m be the unique
number with (q + m + 1)q m+1 < n ≤ (q + m + 2)q m+2 .
As in the proof of Theorem 9 let g1 be the product of
all monic polynomials of degree less than or equal to m
and g2 is some polynomial of degree n−deg(g1 ) . Since
the degree of g1 is at most mq m+1 , the degree of g2
is at least q m+2 . As in the previous lower bound proof,
again only polynomials whose degree is at least m + 1
contribute to some knowledge on g2 . The expected
degree of these polynomials can be upper bounded by
m+3 . In order to reconstruct g2 the sum of the degrees
m+2of these polynomials must be q m+2 and so at least qm+3
examples are needed to do the job. Also only one out ofq m examples qualifies to have at least degree m , so a

2m+2

lower bound for the example complexity is qm+3 . Sincen ≤ (q +m+2)q m+2 and log(n) ≥ m , one can estimate
q 2m+2n2
2−3· (q + m + 2)−1 ≥ q −4 · log(n)and getm+3 ≥ n · q2nexamples arethat, for sufficiently large n , q −4 · log(n)necessary to learn any given polynomial of degree n .
Theorem 9 gives for f (n) = (n + 1)−k , k ∈ IN+ ,directly an algorithm which learns every polynomial gof degree n with average example complexity (n + 2)k .
Considering that every example has to be read throughonce, the time complexity of the algorithm is (n+2)k+1 .
This does not longer work for distributions like f (n)= q −n . Here the lower bound is polynomial, but theupper bound is exponential. Therefore, the next theorem shows how to improve the upper bound from exponential to polynomial time. So both bounds are under this particular distribution quadratic modulo somepoly-logarithmic term.
Theorem 11. There is an algorithm that learns every polynomial from IFq [x] from remainder sequences
drawn at random with respect to the probability distribution generated by f (n) = q −n that needs on average
at most q 7 n2 many examples and time O(n2 log(n))
until convergence on target polynomials of degree n .
Proof. The learner does not use all data-items (a, b)
but only those which belong to irreducible polynomials a . Furthermore, one can divide the polynomial aby its leading coefficient. Note that this division does
not change the remainder b . Thus, we can assume ato be monic without changing the remainder b . Thisnormization enforces that equivalent irreducible polynomials like x2 + 1 and 2x2 + 2 occur only in the form
x2 + 1 . So one makes the polynomials monic and performs a test for irreducibility before further processing.
As a consequence the learning algorithm avoids factoring and similar work. Furthermore before updating its
hypothesis, the learner first checks whether it has already seen the data coming in. This check allows toprocess each irreducible polynomial at most once and toestablish the low time complexity of the learning process. All data, which pass these two checks, are thenused in order to construct a hypothesis about the polynomial to be learned by applying the Chinese Remainder Theorem. As soon as the learner has accumulated asufficient large basis of coprime (even irreducible) polynomials, the target is fully described by its corresponding remainders. We continue with a formal description.
Within the algorithm, (a, b) denotes the current input data, h is a variable standing for the hypothesis
about the polynomial to be learned, L is just the set of
all irreducible polynomials for which the corresponding
remainder of the target is known and d is the productof all polynomials in L . The variable d just keeps thisproduct in order to avoid doing the same multiplication
several times. Now the formal algorithm is presented.
Note that this algorithm outputs only finitely many hy-potheses the last of which will correctly describe thetarget to be learned.

unique polynomial of degree below deg(d) which has,for all a ∈ L , the corresponding remainder b when
divided by a .

Initialize h = 0 , d = 1 and L = ∅ and do
the following for ever:Fourth, there are infinitely many irreducible monicpolynomials a and each a is eventually presented together with the corresponding remainder b . So theevent deg(d) > n must happen eventually and the algorithm converges to the correct hypothesis.

Read (a, b) .
Make a monic, that is, divide a by its leading
coefficient.
If a is irreducible and a ∈/ L thenCompute the remainder c of h modulo a .
Let L = L ∪ {a} .
If b 6= c thenCompute the smallest e suchthat e · d has the remainderb − c modulo a .
Let h = h + e · d .
Output the new hypothesis h .
Let d = a · d .
Continue the loop with reading the next dataitems.
First note that the polynomials in L are all monicand irreducible and thus co-prime. Furthermore, d isalways the product of these polynomials and h satisfies(∃q) [h = aq + b] for all irreducible polynomials a andthe corresponding b seen so far. This can be proved,for every a ∈ L and the corresponding b , as follows:
At some step, the algorithm processes (a, b) in the loop
and the innermost loop guarantees that the new h has
the correct remainder by choosing e such that e · d has
the remainder b − c ; then the sum h + e · d , which gives
the new h , has the remainder c + (b − c) = b modulo
a . In all later steps, a divides d and only terms having
the remainder 0 modulo a are added to h so that thecorrect remainder modulo a is preserved.
Second, it is an invariant of the construction thatdeg(h) < deg(d) : It holds at the initialization (by defining deg(0) < 0 ) and whenever the values of h and d
are updated to h + ed and ad , respectively, then theproperty is preserved since deg(h+ed) < deg(ad) . Thiscan be seen as follows: The degree of ad is the sum
deg(a) + deg(d) . Furthermore, the degree of h + ed
is bounded by max{deg(h), deg(ed)} where deg(h) <deg(d) < deg(a) + deg(d) and deg(ed) = deg(e) +deg(d) < deg(a) + deg(d) . This last relation is basedon the fact that deg(e) < deg(a) and this fact is theconsequence of the observations, that a is irreducible
and so e can be chosen as the smallest representative ofthe quotient (b − c)/d in the field of polynomials modulo a ; this quotient is well-defined since a and d are
co-prime. Note that e = 0 is the solution for the caseb − c = 0 , therefore one can abstain from processing theinner-most loop in this case.
Third, if h0 is the target polynomial and deg(d) >deg(h0 ) , that is, deg(d) > n , then h = h0 since, by the
Chinese Remainder Theorem, h and h0 are both theIt remains to verify the time bound given and to estimate the expected number of examples necessary untilconvergence.
First, we compute the number of examples necessary.
For that purpose it suffices to ask how many examples
are necessary until d has reached some degree greaterthan n . To get such an estimation, let m be the leastdegree such that there are 2nm irreducible polynomialsof degree m in IFq [x] . Using the lower boundIm >q m − q m/2+1
mon the number Im of monic irreducible polynomialsof degree m in IFq [x] (cf. Berlekamp [3]), we obtainthat 2n is near to q m , more precisely, that q m−2 <2n < q m+2 . As long as less than n of the irreducible
polynomials of degree m have occurred in the data
seen so far, the probability of getting one further onenof them is m
· q −2m−1 where q −m−1 is the probability of getting a polynomial of degree at least m andn −mis a lower bound for the probability that thismqpolynomial is among the still unseen irreducible polynomials of degree at least m . The expected number ofndifferent irreducible
examples necessary to receive mpolynomials of degree at least m can therefore be estimated by the upper bound q 2m+1 . The degree of
their product is n so that after q 2m+1 many examples
the size of d is n . Note that 2n > q m−2 and thus
q 2m+1 ≤ 4n2 · q 5 ≤ q 7 n2 . So q 7 n2 is an upper boundon the expected number of examples needed until convergence.
Now the complexity of each step is analyzed. There
are two parts, which have to be dealt separately with:(a) the part which is done for every data-item, and(b) the part within the first “if”-statement after the“then” which is not executed for most of the dataitems.
The part (a) consists of reading the hypothesis of(a, b) , the check whether a is irreducible and the test
whether a ∈ L . The test whether a ∈ L has the timecomplexity deg(a) log(|L|) by keeping L as an ordered
list. The size of L does not exceed n . So for each dataitem, the computations of type (a) need with probability q −k−1 the time p(k) log(n) for some polynomial p .
Since the sum over q −k−1 p(k) converges to some constant r , the step has time complexity r log(n) for eachsingle data item and time complexity rq 7 n2 log(n) in
total.
In part (b) let k denote the degree of a . The degreeof d and the size of L do not exceed n when entering
this part of the algorithm. Now computing the remainder c needs O(nk) time steps and gives a polynomial of
degree below k . b − c is computed in O(k) time steps,
e is computed in O(nk) steps where e is obtained bytaking the smallest representative of the quotient b−cdin the field generated by the irreducible polynomial a ,the multiplication e · d needs O(nk) time steps, theaddition to and update of h needs O(n) steps, theproduct ad is computed within O(nk) time steps, theupdate of d to ad needs O(n) time steps and the update of L needs O(n) time steps (cf. [4]). So a single
run through part (b) needs r0 nk time steps where r0
is some constant. During the whole time, the degrees ofthe polynomials summed up satisfy k1 +k2 +. . .+klast ≤n + klast . Hereby it can be estimated that klast does
not exceed n with reasonable probability. So one hasthat all runs through part (b) together have time complexity r0 (k1 + k2 + . . . + klast )n ≤ 2r0 n2 .
The total example complexity of the algorithm has
the upper bound q 7 n2 and the time complexity has upper bound (rq 7 log(n)+2r0 )n2 , that is, O(n2 log(n)) .
The next example illustrates the learning algorithmof Theorem 11 for a concrete polynomial over the finite
field with three elements.
Example 12. Assume that the polynomial x3 in
IF3 [x] should be learned; note that −1 = 2 in IF3 .
Consider some data-sequence starting with (x2 , 0) ,(x2 + 2, 2x) , (x+1, 2) , (x+2, 1) , (x2 +1, 2x) , (x+1,2) , (x, 0) , (a(x), b(x)) would be the initial part of thedata-sequence where a(x) is an irreducible and monicpolynomial not seen before. From these data-items,(x2 , 0) and (x2 + 2, 2x) do not qualify since x2 andx2 + 2 are not irreducible in IF3 . Furthermore, the second occurrence of (x + 1, 2) also does not qualify, sincex + 1 ∈ L after the first occurrence of (x + 1, 2) . The
following table gives now an overview on the values ofthe other variables of the algorithm after executing theinterior loop where data, which did not qualify, is omitted. The current value of h is also always the current
hypothesis.
data-item−(x + 1, 2)(x + 2, 1)(x2 + 1, 2x)(x, 0)(a(x), b(x))

c
−
0
2
x
0
b(x)

e
−
2
1
x
0
0

d
1
x+1
x2 + 2x4 + 2x5 + 2x(x5 + 2x)b(x)

h
0
2
x
x3
x3
x3

If d0 and h0 are the values of d and h from the previous row, then the update rule for these two variables
is d = a·d0 and h = h0 +e·d0 . So, the updates of h arefrom 0 to 0+2·1 = 2 , then from 2 to 2+1·(x+1) = x

and finally from x to (x + 1) + x · (x2 + 2) = x3 . Fromthen on, b − c and thus also e are always 0 and nofurther updates are done, that is, the learner has stabilized on the correct hypothesis x3 . After processing
some data-item, L contains all monic and irreducible
polynomials processed from the beginning up to the current data-item, so after processing (a(x), b(x)) , the content of L are the polynomials x + 1 , x + 2 , x2 + 1 ,x and a(x) .
Since q = 3 and n = 3 , the average number ofexamples needed until successful learning has the upper bound 39 = 19683 . On the one hand, this boundis not optimal, but on the other hand, the above sample sequence was also a bit unrealistic in the sense thatit contained much more useful data than a randomly
distributed sequence of this length would give.

4

Conclusions

The learnability of univariate integer valued polynomials over the natural numbers and univariate polynomials over finite fields has been investigated. For bothcases, we gave lower and upper bounds of the average
example complexity. Measuring the convergence not relative to the degree of a polynomial but relative to ameasure which takes into account also the size of thecoefficients, standard interpolation is not any more thebest possible algorithm. We found a quite natural distribution where the new learning algorithm gives a speedup from polynomial to logarithmic example complexity
on polynomials with small coefficients. Nevertheless,we show that interpolation is an optimally data-efficient
strategy; so no other learning algorithm behaves on all
input-sequences better than interpolation.
Since polynomials over IFq are not uniquely specified by their input-output-behavior, we chose as datarepresentation the remainder modulo other polynomials. In this model, the general gap between lower andupper bound of the example complexity obtained by
optimal learning still is large for many distributions —we hope that future work might narrow this gap. But
we could obtain much tighter results for the concrete
distribution on the remainders induced by f (n) = q −n .

References[1] Angluin, D. (1980). Inductive inference of formal languages from positive data. Information andControl, 45, 117–135.
[2] D. Angluin and C.H. Smith. Inductive inference:
theory and methods. Computing Surveys 15:237–
269, 1983.
[3] E.R. Berlekamp.
Algebraic Coding Theory.
McGraw-Hill, New York, 1968.
[4] D. Bini and V. Pan. Polynomial and Matrix Computations: Volume 1, Fundamental Algorithms.
Birkhäuser, Boston, 1994.

[5] N.H. Bshouty. On learning multivariate polynomials under the uniform distribution. Information
Processing Letters 61(6):303–309, 1997.
[6] N.H. Bshouty and Y. Mansour. Simple learning algorithms for decision trees and multivariate polynomials. in “Proc. 36th Annual Symposium on
Foundations of Computer Science,” pp. 304–311,
IEEE Press 1995.
[7] T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. in “Proc. 8th International Workshop on Algorithmic Learning Theory- ALT’97,” (M. Li and A. Maruoka, Eds.), Lecture
Notes in Artificial Intelligence 1316, pp. 260–276,
Springer-Verlag 1997.
[8] W. Feller. An Introduction to Probability Theory
and its Applications, Vol. 1. John Wiley & Sons,
New York, 1968.
[9] M.E. Gold. Language identification in the limit.
Information and Control, 10:447–474, 1967.
[10] M. Golea. Average case analysis of a learning algorithm for µ -DNF expressions. in “Proc. 2nd
European Conference on Computational Learning
Theory - EuroColt’95,” (P. Vitanyi, Ed.), Lecture
Notes in Artificial Intelligence 904, pp. 342–356,
Springer-Verlag 1995.
[11] D. Haussler, M. Kearns, N. Littlestone and
M.K. Warmuth. Equivalence of models for polynomial learnability. Information and Computation,
95:129–161, 1991.
[12] D.S. Hirschberg, M.J. Pazzani and K.M. Ali. Average case analysis of k-CNF and k-DNF learningalgorithms. in Computational Learning Theory
and Natural Learning Systems, Vol. II: Intersections Between Theory and Experiment, pp. 15–28,
MIT Press 1994.
[13] K.P. Jantke and H.R. Beick. Combining postulates of naturalness in inductive inference. Elektronische Informationsverarbeitung und Kybernetik(EIK) 17:465–484, 1981.
[14] P. Langley and S. Sage. Tractable average-caseanalysis of naive Bayesian classifiers. in “Proc. 16th
International Conference on Machine Learning, pp.
220–228, Morgan Kaufmann 1999.
[15] S. Okamoto and K. Satoh. An average-case analysis of k -nearest neighbor classifier. in “Proc. 1st
International Conference on Case-Based Reasoning Research and Development,” Lecture Notes in
Computer Science 1010, 253–264, Springer-Verlag,
1995.
[16] M.J. Pazzani and W. Sarrett, A framework foraverage case analysis of conjunctive learning algorithms. Machine Learning 9:349–372, 1992.
[17] R. Reischuk and T. Zeugmann. Learning onevariable pattern languages in linear average time.
in “Proc. 11th Annual Conference on Computational Learning Theory - COLT’98,” pp. 198–208,
ACM Press 1998.
[18] R. Reischuk and T. Zeugmann. A complete andtight average-case analysis of learning monomials.
in “Proc. 16th International Symposium on Theoretical Aspects of Computer Science - STACS’99,”
Trier, March 1999, (C. Meinel and S. Tison, Eds.),
Lecture Notes in Computer Science 1563, pp. 414 423, Springer-Verlag 1999.
[19] P. Rossmanith and T. Zeugmann. Learning k variable pattern languages efficiently stochasticallyfinite on average from positive data. in “Proc. 4thInternational Colloquium on Grammatical Inference - ICGI’98,” (V. Honavar and G. Slutzki, Eds.),
Lecture Notes in Artificial Intelligence 1433, pp.
13–24, Springer-Verlag 1998.
[20] J. Stoer. Numerische Mathematik, Vol. 1. SpringerVerlag, Berlin 1989.
[21] L.G. Valiant. A theory of the learnable. Commun. ACM 27:1134-1142, 1984.
[22] K. Wexler and P. Culicover. Formal Principlesof Language Acquisition. MIT Press, Cambridge,
Mass., 1980.