Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-058 | 20th April 2014 22:01

On Learning, Lower Bounds and (un)Keeping Promises

RSS-Feed




TR14-058
Authors: Ilya Volkovich
Publication: 21st April 2014 00:08
Downloads: 1076
Keywords: 


Abstract:

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and equivalence queries) then $EXP^{NP} \not \subseteq P/poly[\mathcal{C}]$ (when $P/poly[\mathcal{C}]$ stands for the class of all languages that can be computed by polynomial size circuits from the class $\mathcal{C}$). Recently, in \cite{KKO13} $EXP^{NP}$ was replaced by $DTIME(n^{\omega(1)})$. Yet for the models of \emph{randomized} exact learning or Valiant's PAC learning, the best result so far is a lower bound against $BPEXP$ (the exponential-time analogue of $BPP$). In this paper, we derive stronger lower bounds as well as some other consequences from \emph{randomized} exact learning and PAC learning algorithms, answering an open question posed in \cite {FortnowKlivans09} and \cite{KKO13}. In particular, we show that

1. If a Boolean circuit class $\mathcal{C}$ has an efficient \emph{randomized} exact learning algorithm or an efficient PAC learning algorithm then $BPTIME(n^{\omega(1)})/1 \not \subseteq \P/poly[\mathcal{C}]$.
(in fact, our result hold even for a more general model of PAC learning with membership queries.)

2. If a Boolean circuit class $\mathcal{C}$ has an efficient \emph{randomized} exact learning algorithm then no strong pseudo-random generators exist in $P/poly[\mathcal{C}]$.

We note that in both cases the learning algorithms need not be \emph{proper} (a learning algorithm is proper if it outputs a hypothesis from the class it learns). The extra bit of advice comes to accommodate the need to keep the promise of bounded away probabilities of acceptance and rejection. The exact same problem arises when trying to prove lower bounds for $BPTIME$ or $MA$ \cite{Barak02, FortnowSanthanam04, vanMelkebeekPervyshev07, Santhanam09}. It has been an open problem to remove this bit. We suggest an approach to settle this problem in our case. Finally, we slightly improve the result of \cite{BFT98} by showing a subclass of $MAEXP$ that requires super-polynomial circuits. Our results combine and extend some of the techniques previously used in \cite{FortnowKlivans09, KKO13} and \cite{Santhanam09}.



ISSN 1433-8092 | Imprint