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.