The Complexity of Trial-and-Error Function Learning

successively more values of g, where, with each value of g, h outputs a conjectured program for g. In this talk, successful learning of g by h involves there being a point after which h repeatedly conjectures the same correct program for g. For example, there is a learner h which, on any integer polynomial g of any unknown degree d, is successful after having seen d+1 points of g.

We are especially interested in polynomial time (in size of data seen)
computable learners h. Unfortunately, it is well known from Pitt (1989), that this restriction need not capture feasibility. Pitt pointed out that unfair postponement tricks which delay hard computations make the same function classes learnable whether the learners are polynomial time or arbitrarily complex computable.

An important question to address is, then, how to avoid these postponement tricks to achieve fair polynomial time learning.

A learner is called postdictively complete iff all available data is
correctly postdicted by each associated conjecture. We will show
how postdictive completeness (and variants thereof) can introduce some
degree of fairness and honest efficiency into trial-and-error learning.
For example, the set of all functions computable in polynomial time
is learnable by a postdictively complete polynomial time learner,
but the set of all functions computable in exponential time is not.
Of course, this latter class is algorithmically postdictively completely learnable. Analyzing the setting of postdictively complete learners, as well as similar notions, is aimed towards a better understanding of fairness in polynomial time learning.

This is joint work with John Case.