Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR21-161 | 16th November 2021 05:17

On Worst-Case Learning in Relativized Heuristica

TR21-161
Authors: Shuichi Hirahara, Mikito Nanashima
Publication: 16th November 2021 17:16
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.