A Complete and Tight Average-Case Analysis of
Learning Monomials
Rüdiger Reischuk 1 , ? and Thomas Zeugmann 2 , ??
1

Institut für Theoretische Informatik, Med. Universität zu Lübeck, Wallstraße 40,
23560 Lübeck, Germany
reischuk@informatik.mu-luebeck.de
2
Department of Informatics, Kyushu University, Kasuga 816-8580, Japanthomas@i.kyushu-u.ac.jp

Abstract. We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced.
Based on it we consider the problem of learning monomials and the special case of learning monotone monomials in the limit and for on-line
predictions in two variants: from positive data only, and from positive
and negative examples. The well-known Wholist algorithm is completely
analyzed, in particular its average-case behavior with respect to the classof binomial distributions. We consider different complexity measures: thenumber of mind changes, the number of prediction errors, and the total learning time. Tight bounds are obtained implying that worst casebounds are too pessimistic. On the average learning can be achieved
exponentially faster.
Furthermore, we study a new learning model, stochastic finite learning,in which, in contrast to PAC learning, some information about the underlying distribution is given and the goal is to find a correct (not only
approximatively correct) hypothesis. We develop techniques to obtain
good bounds for stochastic finite learning from a precise average caseanalysis of strategies for learning in the limit and illustrate our approachfor the case of learning monomials.

1. Introduction
Learning concepts efficiently has attracted considerable attention during thelast decade. However, research following the traditional lines of inductive inference has mainly considered the update time, i.e., the effort to compute asingle new hypothesis. Starting with Valiant’s paper [18], the total amount oftime needed to solve a given learning problem has been investigated as well. The?

Part of this work was performed while visiting the Department of Informatics at
Kyushu University supported by the Japan Society for the Promotion of Science
under Grant JSPS 29716102.
??
Supported by the Grant-in-Aid for Scientific Research in Fundamental Areas fromthe Japanese Ministry of Education, Science, Sports, and Culture under grantno. 10558047.

complexity bounds proved within the PAC model are usually worst-case bounds.
In experimental studies large gaps have often been observed between the timebounds obtained by a mathematical analysis and the actual runtime of a learneron typical data. This phenomenon can be explained easily. Data from runningtests provide information about the average-case performance of a learner, rather
than its worst-case behavior. Since algorithmic learning has a lot of practical applications it is of great interest to analyze the average-case performance, and toobtain tight bounds saying something about the typical behavior in practice.
Pazzani and Sarrett [14] have proposed a framework for analyzing the averagecase behavior of learning algorithms. Several authors have followed their approach (cf., e.g., [12, 13]). Their main goal is to predict the expected accuracy ofthe hypothesis produced with respect to the number of training examples. However, the results obtained so far are not satisfactory. Typically, the probability
that a random example is misclassified by the current hypothesis is estimatedby a complicated formula. The evaluation of this formula, and the computationof the corresponding expectation has been done by Monte-Carlo simulations.
Clearly, such an approach does not provide general results about the averagecase behavior for broader classes of distributions. Moreover, it is hard to compare
these bounds with those proved for the PAC model.
We outline a new setting to study the average-case behavior of learning algorithms overcoming these drawbacks and illustrate it for learning monomials.
2. Preliminaries
Let N = {0, 1, 2, . . .} be the set of all natural numbers, and let N+ := N\{0} .
If M is a set, |M | is used for its cardinality. For an infinite sequence d andj ∈ N+ let d[j] denote the initial segment of d of length j . By (0, 1) wedenote the real interval from 0 to 1 excluding both endpoints. For n ∈ N+ ,let Xn = {0, 1}n be the learning domain and ℘(Xn ) the power set of Xn . A
subset c of Xn is called a concept, and a subset C of ℘(Xn ) a concept class.
The notation c is also used to denote the characteristic function of a subset, thatis for b ∈ Xn : c(b) = 1 iff b ∈ c. To define the classes of concepts we deal with in
this paper let Ln = {x1 , x̄1 , x2 , x̄2 . . . , xn , x̄n } be a set of literals. xi is a positive
literal and x̄i a negative one. A conjunction of literals defines a monomial. Fora monomial m let #(m) denote its length, that is the number of literals in it.
m describes a subset L(m) of Xn , in other words a concept, in the obvious
way: the concept contains exactly those binary vectors for which the monomial
evaluates to 1, that is L(m) := {b ∈ Xn m(b) = 1} . The collection of objects
we are going to learn is the set Cn of all concepts that are describable bymonomials over Xn . There are two trivial concepts, the empty subset and Xn
itself. Xn , which will also be called “TRUE”, can be represented by the empty
monomial. The concept “FALSE” has several descriptions. To avoid ambiguity,
we always represent “FALSE” by the monomial x1 x̄1 . . . xn x̄n . Furthermore, we
often identify the set of all monomials over Ln and the concept class Cn . Notethat |Cn | = 3n +1. We also consider the subclass MC n of Cn consisting of thoseconcepts that can be described by monotone monomials, i.e., by monomials
containing positive literals only. It holds |MC n | = 2n .

3. Learning Models and Complexity Measures
The first learning model we are dealing with is the on-line prediction model
going back to Barzdin, Freivald [1] and Littlestone [10]. In this setting the sourceof information is specified as follows. The learner is given a sequence of labeled
examples d = hdj ij∈N+ = hb1 , c(b1 ), b2 , c(b2 ), b3 , c(b3 ), . . .i from the conceptc, where the bj ∈ Xn , and c(bj ) = 1 if bj ∈ c and c(bj ) = 0 otherwise. The
examples bj are picked arbitrarily and the information provided is assumed to
be without any errors. We refer to such sequences as data sequences and use
data(c) to denote the set of all data sequences for concept c.
A learner P must predict c(bj ) after having seen d[2j − 1] = hb1 , c(b1 ), . . . ,bj−1 , c(bj−1 ), bj i. We denote this hypothesis by P (d[2j−1]) . Then it receives thetrue value c(bj ) and the next Boolean vector bj+1 . The learner has successfully
learned if it eventually reaches a point beyond which it always predicts correctly.
Definition 1. A concept class C is called on-line predictable if there is alearner P such that for all concepts c ∈ C and all data sequences d = hdj ij∈N+ ∈data(c) it holds: P (d[2j − 1]) is defined for all j , and P (d[2j − 1]) = d2j for all
but finitely many j .
For on-line prediction, the complexity measure considered is the numberof prediction errors made. Note that the prediction goal can always be achieved
trivially if the learning domain is finite. Therefore, we aim to minimize thenumber of prediction errors when learning monomials.
Next, let us define Gold-style [5] learning in the limit. One distinguishes
between learning from positive and negative data, and learning from positive
data only. For a concept c, let info(c) be the set of those data sequences
hb1 , c(b1 ), b2 , c(b2 ), b3 , c(b3 ), . . .i in data(c) that contain each element b of thelearning domain Xn at least once. Such a sequence is called informant. Forease of notation let us pair each element bj with its classification c(bj ) . Thenthe j -th entry of an informant sequence d will be dj := (bj , c(bj )) .
A positive presentation of c is a data sequence that contains only elementsof c and each one at least once. Thus all the values c(bj ) are equal to 1 andthus could be omitted. In this case we will denote the sequence simply by d =hdj ij∈N+ = hb1 , b2 , b3 , ...i. Let d[j]+ := {bi 1 ≤ i ≤ j} be the set of all examples
contained in the prefix of d of length j , and let pos(c) denote the set of all
positive presentations of c. The elements of pos(c) are also called a text for c.
A limit learner is an inductive inference machine (abbr. IIM). An IIM
M works as follows. As inputs it gets incrementally growing segments of a positive presentation (resp. of an informant) d . After each new input, it outputs
a hypothesis M (d[j]) from a predefined hypothesis space H . Each hypothesis
refers to a unique element of the concept class.
Definition 2. Let C be a concept class and let H be a hypothesis space forit. C is called learnable in the limit from positive presentation (resp. frominformant) if there is an IIM M such that for every c ∈ C and every d ∈ pos(c)(resp. d ∈ info(c)): M (d[j]) is defined for all j , and M (d[j]) = h for all but
finitely many j , where h ∈ H is a hypothesis referring to c.

For the concept class Cn we choose as hypothesis space the set of all monomials over Ln , whereas for MC n it is the set of all monotone monomials. Again,
we are interested how efficiently Cn and MC n can be learned in the limit.
The first complexity measure we consider is the mind change complexity.
A mind change occurs iff M (d[j]) 6= M (d[j + 1]) . Clearly, this measure is closely
related to the number of prediction errors. Both complexity measures say little
about the total amount of data and time needed until a concept is guessed
correctly. Thus, for learning in the limit we also measure the time complexity.
As in [3] we define the total learning time as follows. Let M be any IIM learninga concept class C in the limit. Then, for c ∈ C and a text or informant d for c, letCon(M, d) = the least i ∈ N+ such that M (d[j]) = M (d[i]) for all j ≥ idenote the stage of convergence of M on d (cf. [5]). Moreover, by TM (dj ) we
denote the number of steps to compute M (d[j]) . We measure this quantity as
a function of the length of the input and refer to it as the update time. Finally,
the total learning time taken by the IIM M on a sequence d is defined asPCon(M,d)T T (M, d) :=TM (d[j]) . Given a probability distribution D on
j=1
the data sequences d we evaluate the expectation of T T (M, d) with respect
to D , the average total learning time.
4. The Wholist Algorithm Learning Monomials
Next, we present Haussler’s [6] Wholist algorithm for on-line prediction ofmonomials. For learning in the limit this algorithm can be modified straightforwardly. The limit learner computes a new hypothesis using only the mostrecent example received and his old hypothesis. Such learners are called iterative(cf. [8]). Let c ∈ Cn , let d ∈ data(c) , and let bi = b1i b2i . . . bni denote the i-th
Boolean vector in d . Recall that “TRUE” is represented by the empty monomial.
Algorithm P: On input sequence hb1 , c(b1 ), b2 , c(b2 ), . . .i do the following:
Initialize h0 := x1 x̄1 . . . xn x̄n .
for i = 1, 2, . . . dolet hi−1 denote P’s internal hypothesis produced before receiving bi ;when receiving bi predict hi−1 (bi ) ; read c(bi ) ;if hi−1 (bi ) = c(bi ) then hi := hi−1else for j := 1 to n do
if bji = 1 then delete x̄j in hi−1 else delete xj in hi−1 ;let hi be the resulting monomial
end.
Note that the algorithm is monotone with respect to the sequence of its
internal hypotheses: hi ≥ hi−1 when considered as function on Xn .
Theorem 1. Algorithm P learns the set of all monomials within the prediction
model. It makes at most n + 1 prediction errors.
To learn the monotone concept class MC n , algorithm P can be easily modified by initializing h0 = x1 x2 . . . xn and by simplifying the loop appropriately.
We refer to the modified algorithm as to MP.
Theorem 1 can be directly reproved for MP with the only difference that
now the worst-case bound for the number of prediction errors is n instead ofn + 1.

5. Complexity Analysis: Best and Worst Case
For the learning models defined above we estimate the best-case complexity,
the worst-case complexity, and the expectation of algorithm P and MP. We
start with the first two issues. Both algorithms do not make any prediction errors
iff the initial hypothesis h0 equals the target monomial. For P this means thatthe concept to be learned is “FALSE”, while for MP the concept is the all-1
vector. These special concepts can be considered as minimal in their class. Forthem the best-case and the worst-case number of predictions errors coincide.
In the general case, we call the literals in a monomial m relevant. All otherliterals in Ln (resp. in {x1 , . . . , xn } in the monotone case) are said to be irrelevant for m . There are 2n − #(m) irrelevant literals in general, and n − #(m)in the monotone case. We call bit i relevant for m if xi or x̄i is relevant form. By k = k(m) = n − #(m) we denote the number of irrelevant bits.
Theorem 2. Let c = L(m) be a non-minimal concept in MC n . Then algorithm
MP makes 1 prediction error in the best case, and k(m) prediction errors in
the worst-case.
If c is a non-minimal concept of Cn algorithm P makes 2 prediction errors inthe best case and 1 + k(m) prediction errors in the worst-case.
As Theorem 2 shows, the gap between the best-case and worst-case behavior
can be quite large. Thus, we ask what are the expected bounds for the number ofprediction errors on randomly generated data sequences. Before answering thisquestion we estimate the worst-case number of prediction errors averaged over
the whole concept class MC n , resp. Cn . Thus we get a complexity bound withrespect to the parameter n , instead of #(m) as in Theorem 2. This averaging
depends on the underlying probability distribution for selecting the target concepts (for the corresponding data sequences we consider the worst input). The
average is shown to be linear in n if the literals are binomially distributed.
To generate the probability distributions we assume for MC n the relevant
positive literals to be drawn independently at random with probability p , p ∈(0, 1). Thus, with probability 1−p a literal is irrelevant. The length of the monomials drawn by this distribution is binomially distributed with parameter p .
Thus we call such a distribution on the concept class a binomial distribution.
Theorem 3. Let the concepts in MC n be binomially distributed with parameter p . Then the average number of prediction errors of MP for the worst data
sequences is n(1 − p).
In case p = 1/2, the bound says that the maximal number of prediction
errors when uniformly averaged over all concepts in MC n is n/2 .
Next, we deal with the class Cn . For comparing it to the monotone case wehave to clarify what does it mean for concepts in Cn to be binomially distributed.
Since there are 3n + 1 many concepts in Cn for a uniform distribution each concept must have probability 1/(3n + 1) . For each position i = 1, . . . , n three options are possible,
 i.e., we may choose xi , x̄i or neither of them. This suggests theformula k1 ,kn2 ,k3 pk11 pk22 pk33 , where p1 is the probability to take xi , p2 the probability to choose x̄i and p3 the probability to choose none, and p1 + p2 + p3 = 1

and k1 + k2 + k3 = n . k1 + k2 counts the number of relevant literals, resp. bits.
However, this formula does not include the concept “FALSE.” Thus, let us introduce pf ∈ (0, 1) for the probability to choose “FALSE.” Then the formula
becomes (1 − pf ) k1 ,kn2 ,k3 p1k1 pk22 pk33 . We call such a probability distribution aweighted multinomial distribution with parameters (pf , p1 , p2 , p3 ) .
Theorem 4. Let the concepts in Cn occur according to a weighted multinomial distribution with parameters (pf , p1 , p2 , p3 ). Then the average number ofprediction errors of P for the worst data sequences is (1 − pf )(1 + np3 ).
For the particular case that all concepts from Cn are equally likely, i.e.,
p1 = p2 = p3 = 1/3 and pf = 1/(3n +1) , we directly get that on the average lessthan n/3 + 1 errors are to be expected given the worst data sequences. Hence,in this case the class Cn seems to be easier to learn than MC n with respect
to the complexity measure prediction errors. However, this impression is a bit
misleading, since the probabilities to generate an irrelevant literal are different,i.e., 1/3 for Cn and 1/2 for MC n . If we assume the probabilities to generate anirrelevant literal to be equal, say q , and make the meaningful assumption that
“FALSE” has the same probability as “TRUE” then the average complexity is
1
1+q n (1+nq) for Cn and nq for MC n . Since for Cn it holds q = 1−(p1 +p2 ) ,and for MC n q = 1−p , under these assumptions MC n is easier to learn than Cn .
This insight is interesting, since it clearly shows the influence of the underlying
distribution. In contrast, previous work has expressed these bounds in terms of
the VC-dimension which is the same for both classes, i.e., n .
The results above directly translate to learning in the limit from informant orfrom positive presentations for the complexity measure number of mind changes.
What can be said about the total learning time? The best-case can be handled
as above. Sine the update time is linear in n for both algorithms MP and P, inthe best case the total learning time is linear. The worst-case total learning timeis unbounded for both algorithms, since every text and informant may contain as
many repetitions of data not possessing enough information to learn the target.
Hence, as far as learning in the limit and the complexity measure total learning time are concerned, there is a huge gap between the best-case and the worstcase behavior. Since the worst-case is unbounded, it does not make sense to
ask for an analogue to Theorem 3 and 4. Instead, we continue by studying the
average-case behavior of the limit learner P and MP.
6. Average-Case Analysis for Learning in the Limit from Text
For the following average case analysis we assume that the data sequences
are generated at random with respect to some probability distribution D takenfrom a class of admissible distributions D specified below. We are interested
in the average number of examples till an algorithm has converged to a correct
hypothesis. CON denotes a random variable counting the number of examples
till convergence. Let d be a text of the concept c to be learned that is generated
at random according to D . If the concept to be learned is “FALSE” no examples
are needed. Otherwise, if the target concept contains precisely n literals thenone positive example suffices (note that this one is unique). Thus, for thesetwo cases everything is clear and the probability distributions D on the set of
positive examples for c are trivial.
For analyzing the nontrivial cases, let c = L(m) ∈ Cn be a concept withV#(m)monomial m = j=1 `ij such that k = k(m) = n − #(m) > 0 . There are 2k
positive examples for c. For the sake of presentation, we assume these examples
to be binomially distributed. That is, in a random positive example all entries
corresponding to irrelevant bits are selected independently of each other. With
some probability p this will be a 1 , and with probability q := 1−p a 0 . We shallconsider only nontrivial distributions where 0 < p < 1 . Note that otherwise thedata sequence does not contain all positive examples. We aim to compute theexpected number of examples taken by P until convergence.
The first example received forces P to delete precisely n of the 2n literals
in h0 . Thus, this example always plays a special role. Note that the resulting
hypothesis h1 depends on b1 , but the number k of literals that remain to bedeleted from h1 until convergence is independent of b1 . Using tail bound techniques, we can show the following theorem.
Theorem 5. Let c = L(m) be a non-minimal concept in Cn , and let the positive examples for c be binomially distributed with parameter p . Define ψ :=1
, p1 } . Then the expected number of positive examples needed by algomin{ 1−prithm P until convergence can be bounded by E[CON] ≤ dlogψ k(m)e + 3 .
A similar analysis can be given in the monotone setting for algorithm MP.
Corollary 6. For every binomially distributed text with parameter 0 < p < 1
the average total learning time of algorithm P for concepts in Cn with µ literals
is at most O(n(log(n − µ + 2)).
The expectation alone does not provide complete information about the average case behavior of an algorithm. We also like to deduce bounds on how often
the algorithm exceeds the average considerably. The Wholist algorithm possesses
two favorable properties that simplify this derivation considerably, i.e., it is setdriven and conservative. Set-driven means that for all c ∈ Cn all d, h ∈ pos(c)and all i, j ∈ N+ the equality d[i]+ = h[j]+ implies P(d[i]) = P(h[j]) . A learneris said to be conservative if every mind change is caused by an inconsistency withthe data seen so far. Clearly, the Wholist algorithm satisfies this condition, too.
Now, the following theorem establishes exponentially shrinking tail bounds forthe expected number of examples needed in order to achieve convergence.
Theorem 7 ([16]). Let CON be the sample complexity of a conservative and setdriven learning algorithm. Then Pr[CON > 2 t · E[CON]] ≤ 2−t for all t ∈ N .
A simple calculation shows that in case of exponentially shrinking tail bounds
the variance is bounded by O(E[CON]2 ) .
7. Stochastic Finite Learning
Next we shall show how to convert the Wholist algorithm into a text learnerthat identifies all concepts in Cn stochastically in a bounded number of roundswith high confidence. A bit additional knowledge concerning the underlying classof probability distributions is required. Thus, in contrast to the PAC model, theresulting learning model is not distribution-free. But with respect to the qualityof its hypotheses, it is stronger than the PAC model by requiring the output tobe probably exactly correct rather than probably approximately correct. The main
advantage is the usage of the additional knowledge to reduce the sample size,and hence the total learning time drastically. This contrasts to previous work in
the area of PAC learning (cf., e.g., [2, 4, 7, 9, 11, 17]). These papers have shown
concepts classes to be PAC learnable from polynomially many examples given aknown distribution or class of distributions, while the general PAC learnability ofthese concepts classes is not achievable or remains open. Note that our generalapproach, i.e., performing an average-case analysis and proving exponentiallyshrinking tail bounds for the expected total learning time, can also be applied
to obtain results along this line (cf. [15, 16]).
Definition 3. Let D be a set of probability distributions on the learning domain,
C a concept class, H a hypothesis space for C , and δ ∈ (0, 1). (C, D) is said tobe stochastically finite learnable with δ -confidencewith respect to H iff
there is an IIM M that for every c ∈ C and every D ∈ D performs as follows.
Given a random presentation d for c generated according to D , M stops after
having seen a finite number of examples and outputs a single hypothesis h ∈ H .
With probability at least 1 − δ (with respect to distribution D ) h has to becorrect, that is L(h) = c in case of monomials. If stochastic finite learning canbe achieved with δ -confidence for every δ > 0 then we say that (C, D) can belearned stochastically finite with high confidence.
We study the case that the positive examples are binomially distributed withparameter p . But we do not require precise knowledge about the underlying distribution. Instead, we reasonably assume that prior knowledge is provided by parameters plow and pup such that plow ≤ p ≤ pup for the true parameter p . Binomial distributions fulfilling this requirement are called (plow , pup ) –admissible
distributions. Let Dn [plow , pup ] denote the set of such distributions on Xn .
If bounds plow and pup are available, the Wholist algorithm can be transformed into a stochastic finite learner inferring all concepts with high confidence.
Theorem 8. Let 0 < plow ≤ pup < 1 and ψ := min{ 1−p1 low , p1up }. Then
(Cn , Dn [plow , pup ]) is stochastically finitely learnable with high confidence frompositive presentations. To achieve δ -confidence no more than O(log2 1/δ ·logψ n)many examples are necessary.
The latter example bound can even be improved to logψ n + logψ 1/δ + O(1) byperforming a careful error analysis, i.e., for the Wholist algorithm, the confidence
requirement increases the sample size by an additive term logψ 1/δ only.
8. Average-case Analysis for Learning in the Limit from Informant
Finally, we consider how the results obtained so far translate to the case oflearning from informant. First, we investigate the uniform distribution over Xn .
Again, we have the trivial cases that the target is “FALSE” or m is a monomial
without irrelevant bits. In the first case, no example is needed at all, while in thelatter one, there is only one positive example having probability 2−n . Thus the
expected number of examples needed until successful learning is 2n = 2#(m) .

Theorem 9. Let c = L(m) ∈ Cn be a nontrivial concept. If an informant
for c is generated from the uniform distribution by independent draws the expected number of examples needed by algorithm P until convergence is boundedby E[CON] ≤ 2#(m) (dlog2 k(m)e + 3) .
Hence, as long as k(m) = n−O(1) , we still achieve an expected total learning
time O(n log n). But if #(m) = Ω(n) the expected total learning is exponential.
However, if there are many relevant literals then even h0 may be considered asa not too bad approximation for c. Thus, let ε ∈ (0, 1) be an error parameter asin the PAC model. We ask if one can achieve an expected sample complexity forcomputing an ε -approximation that is polynomially bounded in log n and 1/ε .
Let err m (hj ) := D(L(hj ) 4 L(m)) be the error made by hypothesis hj withrespect to monomial m . Here L(hj )4L(m) is the symmetric difference of L(hj )and L(m), and D the probability distribution with respect to which the examples are drawn. hj is an ε–approximation for m if err m (hj ) ≤ ε . Finally, we
redefine the stage of convergence. Let d = (dj )j∈N+ ∈ info(L(m)) , thenCONε (d) = the least number j such that err m (P (d[i])) ≤ ε for all i ≥ j .
Note that once the Wholist algorithm has reached an ε -approximate hypothesis all further hypotheses will also be at least that close to the target monomial.
The following theorem gives an affirmative answer to the question posed above.
Theorem 10. Let c = L(m) ∈ Cn be a nontrivial concept. Assuming that examples are drawn independently from the uniform distribution, the expected numberof examples needed by algorithm P until converging to an ε -approximation for c
can be bounded by E[CONε ] ≤ 1ε · (dlog2 k(m)e + 3) .
Thus, additional knowledge concerning the underlying probability distribution pays off again. Using Theorem 7 and modifying Section 7 mutatis mutandis,
we achieve stochastic finite learning with high confidence for all concepts in Cn
using O( 1ε · log 1δ · log n) many examples. However, the resulting learner now infers ε -approximations. Comparing this bound with the sample complexity givenin the PAC model one notes an exponential reduction.
Finally, we generalize the last results to the case that the data sequences
are binomially distributed for some parameter p ∈ (0, 1) . This means that any
particular vector containing ν times a 1 and n − ν a 0 has probability pν (1 −p)n−ν since a 1 is drawn with probability p and a 0 with probability 1 − p .
First, Theorem 9 generalizes as follows.
Theorem 11. Let c = L(m) ∈ Cn be a nontrivial concept. Let m contain precisely π positive literals and τ negative literals. If the labeled examples for c are1
independently binomially distributed with parameter p and ψ := min{ 1−p, p1 }
then the expected number of examples neededby algorithmP until convergence
1
can be bounded by E[CON] ≤ pπ (1−p)τ dlogψ k(m)e + 3 .
Theorem 10 directly translates into the setting of binomially distributed inputs.
Theorem 12. Let c = L(m) ∈ Cn be a nontrivial concept. Assume that theexamples are drawn with respect to a binomial distribution with parameter p ,1
and let ψ = min{ 1−p, p1 } . Then the expected number of examples needed byalgorithm P until converging to an ε -approximation for c can be bounded by
E[CON] ≤ 1ε · (dlogψ k(m)e + 3) .

Finally, one can also learn ε -approximations stochastically finite with highconfidence from informant with an exponentially smaller sample complexity.
Theorem 13. Let 0 < plow ≤ pup < 1 and ψ := min{ 1−p1 low , p1up } . For(Cn , Dn [plow , pup ]) ε -approximations are stochastically finitely learnable with δ confidence from informant for all ε, δ ∈ (0, 1). Further, O 1ε · log2 1/δ · logψ n ,
resp. O 1ε · (logψ 1/δ + logψ n) many examples suffice for this purpose.

References
1. J.M. Barzdin, R.V. Freivald, On the prediction of general recursive functions. Soviet Math. Doklady 13:1224-1228, 1972.
2. G. Benedek and A. Itai. Learnability by fixed distributions. “Proc. 1988 Workshop
on Computational Learning Theory,” 81–90, Morgan Kaufmann, 1988.
3. R. Daley and C.H. Smith. On the complexity of inductive inference. Inform. Control, 69:12–40, 1986.
4. F. Denis and R. Gilleron. PAC learning under helpful distributions. “Proc. 8thInternational Workshop on Algorithmic Learning Theory,” LNAI Vol. 1316, 132–
145, Springer-Verlag, 1997.
5. E.M. Gold, Language identification in the limit. Inform. Control 10:447–474, 1967.
6. D. Haussler. Bias, version spaces and Valiant’s learning framework. “Proc. 8th
National Conference on Artificial Intelligence, 564–569, Morgan Kaufmann, 1987.
7. M. Kearns, M. Li, L. Pitt and L.G. Valiant. On the learnability of Boolean formula.
“Proc. 19th Annual ACM Symposium on Theory of Computing,” 285–295, ACM
Press 1987.
8. S. Lange and T. Zeugmann. Incremental learning from positive data. J. Comput. System Sci. 53(1):88–103, 1996.
9. M. Li and P. Vitanyi. Learning simple concepts under simple distributions. SIAM
J. Comput., 20(5):911-935, 1991.
10. N. Littlestone. Learning quickly when irrelevant attributes are abound: A newlinear threshold algorithm. Machine Learning 2:285–318, 1988.
11. B. Natarajan. On learning Boolean formula. “Proc. 19th Annual ACM Symposiumon Theory of Computing,” 295–304, ACM Press, 1987.
12. S. Okamoto and K. Satoh. An average-case analysis of k -nearest neighbor classifier. “Proc. 1st International Conference on Case-Based Reasoning Research andDevelopment,” LNCS Vol. 1010, 253–264, Springer-Verlag, 1995.
13. S. Okamoto and N. Yugami. Theoretical analysis of the nearest neighbor classifierin noisy domains. “Proc. 13th International Conference on Machine Learning,
355–363, Morgan Kaufmann 1996.
14. M.J. Pazzani and W. Sarrett, A framework for average case analysis of conjunctive
learning algorithms. Machine Learning 9:349–372, 1992.
15. R. Reischuk and T. Zeugmann. Learning one-variable pattern languages in linear
average time. “Proc. 11th Annual Conference on Computational Learning Theory,”
198–208, ACM Press, 1998.
16. P. Rossmanith and T. Zeugmann. Learning k -variable pattern languages efficiently
stochastically finite on average from positive data. “Proc. 4th International Colloquium on Grammatical Inference,” LNAI Vol. 1433, 13–24, Springer-Verlag, 1998.
17. Y. Sakai, E. Takimoto and A. Maruoka. Proper learning algorithms for functionsof k terms under smooth distributions. “Proc. 8th Annual ACM Conference on
Computational Learning Theory,” 206–213, ACM Press, 1995.
18. L.G. Valiant. A theory of the learnable. Commun. ACM 27:1134-1142, 1984.