Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes

This work initiates a general study of learning and generalization without\nthe i.i.d. assumption, starting from first principles. While the traditional\napproach to statistical learning theory typically relies on standard\nassumptions from probability theory (e.g., i.i.d. or stationary ergodic), in\nthis work we are interested in developing a theory of learning based only on\nthe most fundamental and necessary assumptions implicit in the requirements of\nthe learning problem itself. We specifically study universally consistent\nfunction learning, where the objective is to obtain low long-run average loss\nfor any target function, when the data follow a given stochastic process. We\nare then interested in the question of whether there exist learning rules\nguaranteed to be universally consistent given only the assumption that\nuniversally consistent learning is possible for the given data process. The\nreasoning that motivates this criterion emanates from a kind of optimist's\ndecision theory, and so we refer to such learning rules as being optimistically\nuniversal. We study this question in three natural learning settings:\ninductive, self-adaptive, and online. Remarkably, as our strongest positive\nresult, we find that optimistically universal learning rules do indeed exist in\nthe self-adaptive learning setting. Establishing this fact requires us to\ndevelop new approaches to the design of learning algorithms. Along the way, we\nalso identify concise characterizations of the family of processes under which\nuniversally consistent learning is possible in the inductive and self-adaptive\nsettings. We additionally pose a number of enticing open problems, particularly\nfor the online learning setting.\n