Title: Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes,
Abstract: This work initiates a general study of learning and generalization without
the i.i.d. assumption, starting from first principles. While the standard
approach to statistical learning theory is based on assumptions chosen largely
for their convenience (e.g., i.i.d. or stationary ergodic), in this work we are
interested in developing a theory of learning based only on the most
fundamental and natural assumptions implicit in the requirements of the
learning problem itself. We specifically study universally consistent function
learning, where the objective is to obtain low long-run average loss for any
target function, when the data follow a given stochastic process. We are then
interested in the question of whether there exist learning rules guaranteed to
be universally consistent given only the assumption that universally consistent
learning is possible for the given data process. The reasoning that motivates
this criterion emanates from a kind of optimist's decision theory, and so we
refer to such learning rules as being optimistically universal. We study this
question in three natural learning settings: inductive, self-adaptive, and
online. Remarkably, as our strongest positive result, we find that
optimistically universal learning rules do indeed exist in the self-adaptive
learning setting. Establishing this fact requires us to develop new approaches
to the design of learning algorithms. Along the way, we also identify concise
characterizations of the family of processes under which universally consistent
learning is possible in the inductive and self-adaptive settings. We
additionally pose a number of enticing open problems, particularly for the
online learning setting.