Learning in Pessiland via Inductive Inference

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no oneway function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.

In this paper, we develop a unified framework for constructing strong learning algorithms under the nonexistence of a one-way function, indicating a positive aspect of Pessiland. Using our framework, we improve the learning algorithm for adaptively changing distributions, which was introduced by Naor and Rothblum (ICML'06). Although the previous learner assumes the knowledge of underlying distributions, our learner is universal, i.e., does not assume any knowledge on distributions, and has better sample complexity. We also employ our framework to construct a strong agnostic learner with optimal sample complexity, which improves the previous PAC learner of Blum, Furst, Kearns, and Lipton (Crypto'93). Our learning algorithms are worst-case algorithms that run in exponential time with respect to computational depth, and as a by-product, we present the first characterization of the existence of a oneway function by the worst-case hardness of some promise problem in AM. As a corollary of our results, we establish the robustness of average-case learning, that is, the equivalence among various average-case learning tasks, such as (strong and weak) agnostic learning, learning adaptively changing distributions with respect to arbitrary unknown distributions, and weak learning with membership queries with respect to the uniform distribution.

Our framework is based on the theory of Solomonoff's inductive inference and the universal extrapolation algorithm of Impagliazzo and Levin (FOCS'90). Conceptually, the framework demonstrates that Pessiland is, in fact, a wonderland for machine learning in which various learning tasks can be efficiently solved by the generic algorithm of universal extrapolation.