A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption might be sufficient for worst-case learning than the feasibility of worst-case algorithms for NP problems.

In this study, we investigate whether these worst-case requirements for learning are satisfied on the basis of only average-case assumptions in order to understand the nature of learning. First, we construct a strong worst-case learner based on the assumption that DistNP $\subseteq$ AvgP, i.e., in Heuristica. Our learner agnostically learns all polynomial-size circuits on all unknown P/poly-samplable distributions in polynomial time, where the complexity of learning depends on the complexity of sampling examples. Second, we study the limitation of relativizing constructions of learners based on average-case heuristic algorithms. Specifically, we construct a powerful oracle such that DistPH $\subseteq$ AvgP, i.e., every problem in PH is easy on average, whereas UP $\cap$ coUP and PAC learning on almost-uniform distributions are hard even for $2^{n/\omega(\log n)}$-time algorithms in the relativized world, which improves the oracle separation presented by Impagliazzo (CCC 2011). The core concept of our improvements is the consideration of a switching lemma on a large alphabet, which may be of independent interest. The lower bound on the time complexity is nearly optimal because Hirahara (STOC 2021) showed that DistPH $\subseteq$ AvgP implies that PH can be solved in time $2^{O(n / \log n)}$ under any relativized world.