Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond <Emphasis FontCategory="SansSerif">P/poly</Emphasis>, such as <Emphasis FontCategory="SansSerif">PSPACE/poly</Emphasis> and <Emphasis FontCategory="SansSerif">E/poly</Emphasis>.We show the following:<OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> (Unconditional Lower Bounds for Learning) Building on Klivanset al. (2013), we prove unconditionally that <Emphasis FontCategory="SansSerif">BPE/poly</Emphasis> cannot beweakly learned in polynomial time over the uniform distribution,even with membership and equivalence queries. </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> (Robustness of Learning) For the concept classes <Emphasis FontCategory="SansSerif">EXP/poly</Emphasis>and <Emphasis FontCategory="SansSerif">PSPACE/poly</Emphasis>, we unconditionally show that worst-case andaverage-case learning are equivalent, that <Emphasis FontCategory="SansSerif">PAC</Emphasis>-learnability andlearnability over the uniform distribution are equivalent, and thatmembership queries do not help in either case. </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> (Reducing Succinct Search to Decision for Learning) For the decisionproblems <Emphasis FontCategory="SansSerif">R</Emphasis><Emphasis FontCategory="SansSerif">Kt</Emphasis> and <Emphasis FontCategory="SansSerif">R</Emphasis><Emphasis FontCategory="SansSerif">KS</Emphasis> capturing the complexity of learning<Emphasis FontCategory="SansSerif">EXP/poly</Emphasis> and <Emphasis FontCategory="SansSerif">PSPACE/poly</Emphasis>, respectively, we show a succinctsearch to decision reduction: for each of these problems, the problemis in <Emphasis FontCategory="SansSerif">BPP</Emphasis> iff there is a probabilistic polynomial-time algorithmcomputing circuits encoding proofs for positive instancesof the problem. This is shown via a more general result givingsuccinct search to decision results for <Emphasis FontCategory="SansSerif">PSPACE, EXP</Emphasis> and <Emphasis FontCategory="SansSerif">NEXP</Emphasis>,which might be of independent interest. </ItemContent> </ListItem> <ListItem> <ItemNumber>4.</ItemNumber> <ItemContent> (Implausibility of Oblivious Strongly Black-Box Reductions showing<Emphasis FontCategory="SansSerif">NP</Emphasis>-hardness of learning <Emphasis FontCategory="SansSerif">NP/poly</Emphasis>) We define a natural notionof hardness of learning with respect to oblivious strongly blackboxreductions. We show that learning <Emphasis FontCategory="SansSerif">PSPACE/poly</Emphasis> is <Emphasis FontCategory="SansSerif">PSPACE</Emphasis> hardwith respect to oblivious strongly black-box reductions. Onthe other hand, if learning <Emphasis FontCategory="SansSerif">NP/poly</Emphasis> is <Emphasis FontCategory="SansSerif">NP</Emphasis>-hard with respect to oblivious strongly black-box reductions, the polynomial hierarchycollapses. </ItemContent> </ListItem> </OrderedList>

On the Structure of Learnability beyond P/poly

期刊论文
发表日期：

2025年1月6日

查看全文

Ninad Rajgopal,
Rahul Santhanam

摘要

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and E/poly.

We show the following: 1.

(Unconditional Lower Bounds for Learning) Building on Klivanset al. (2013), we prove unconditionally that BPE/poly cannot beweakly learned in polynomial time over the uniform distribution,even with membership and equivalence queries.

(Robustness of Learning) For the concept classes EXP/polyand PSPACE/poly, we unconditionally show that worst-case andaverage-case learning are equivalent, that PAC-learnability andlearnability over the uniform distribution are equivalent, and thatmembership queries do not help in either case.

(Reducing Succinct Search to Decision for Learning) For the decisionproblems R_Kt and R_KS capturing the complexity of learningEXP/poly and PSPACE/poly, respectively, we show a succinctsearch to decision reduction: for each of these problems, the problemis in BPP iff there is a probabilistic polynomial-time algorithmcomputing circuits encoding proofs for positive instancesof the problem. This is shown via a more general result givingsuccinct search to decision results for PSPACE, EXP and NEXP,which might be of independent interest.

(Implausibility of Oblivious Strongly Black-Box Reductions showingNP-hardness of learning NP/poly) We define a natural notionof hardness of learning with respect to oblivious strongly blackboxreductions. We show that learning PSPACE/poly is PSPACE hardwith respect to oblivious strongly black-box reductions. Onthe other hand, if learning NP/poly is NP-hard with respect to oblivious strongly black-box reductions, the polynomial hierarchycollapses.