On worst-case learning in relativized heuristica
S Hirahara, M Nanashima - 2021 IEEE 62nd Annual …, 2022 - ieeexplore.ieee.org
S Hirahara, M Nanashima
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science …, 2022•ieeexplore.ieee.orgA 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 re-quirements for learning …
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 re-quirements for learning …
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 re-quirements 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 ⊆ 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 ⊆ AvgP, i.e., every problem in PH is easy on average, whereas UP ∩ coUP and PAC learning on almost-uniform distributions are hard even for 2 n/w(1og 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 ⊆ AvgP implies that PH can be solved in time 2 O(n/ log n) under any relativized world. The full version of this paper is available on ECCC [1].
ieeexplore.ieee.org