16
$\begingroup$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\mathsf{TC}^0$, since I'm not an expert in the area.

What I've discovered thus far is:

  • All of $\mathsf{AC}^0$ can be learned in quasipolynomial time under the uniform distribution via Linial-Mansour-Nisan.
  • Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of Naor-Reingold that $\mathsf{TC}^0$ admits PRFGs, suggests that $\mathsf{TC}^0$ represents the limits of learnability (at least in a PAC-sense)
  • There's a 2002 paper by Jackson/Klivans/Servedio that can learn a fragment of $\mathsf{TC}^0$ (with at most polylogarithmic majority gates).

I've done the usual google scholaring, but am hoping the collective wisdom of cstheory might have a quicker answer:

Is what I described the state of the art for our understanding of the complexity of learning (in terms of which classes sandwich efficient learners) ? And is there a good survey/reference that maps out the current state of the landscape ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ +1 Nice question. Didn't Lance have a related blog post some time ago? $\endgroup$ – Kaveh Apr 4 '14 at 0:52
  • 1
    $\begingroup$ Do you mean this one (guest post by Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/… $\endgroup$ – Suresh Venkat Apr 4 '14 at 1:38
  • 1
    $\begingroup$ Maybe this one: blog.computationalcomplexity.org/2013/08/… $\endgroup$ – Suresh Venkat Apr 4 '14 at 1:49
  • 1
    $\begingroup$ It is plausible that there are pseudorandom generators in NC0. $\:$ (In particular, I find it very unlikely that a pseudorandom generator is known to prevent learning.) $\;\;\;$ On the other hand, the existence of the maps $\: x\mapsto F(r\hspace{-0.03 in},x) \:$ for a pseudorandom function family $F$ does prevent learning. $\endgroup$ – user6973 Apr 5 '14 at 19:23
  • 3
    $\begingroup$ Linial-Mansour-Nisan show that $\text{AC}^0$ can be learned under the uniform distribution in quasipolynomial time. Kharitinov showed that if quasipolynomial were improved to polynomial, it would yield a sub-exponential time algorithm for factoring Blum integers. $\endgroup$ – Robin Kothari Apr 8 '14 at 1:35
9
$\begingroup$

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov. They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What is the fastest running time known for learning such LTF circuits? (or anything inside $TC^0$) $\endgroup$ – gradstudent Feb 18 '18 at 8:51
5
$\begingroup$

Depth-2 TC0 probably can't be PAC learned in subexponential time over the uniform distribution with a random oracle access. I don't know of a reference for this, but here's my reasoning: We know that parity is only barely learnable, in the sense that the class of parity functions is learnable in itself, but once you do just about anything to it (such as adding a bit of random noise), it ceases being learnable. But depth-2 TC0 is strong enough to represent all parity functions and strong enough to represent perturbed versions of parities, so I think it's safe to guess that depth-2 TC0 cannot be PAC learned.

However, parities and noisy parities can be learned in polynomial time if we're given a membership oracle. So it might be interesting to check whether depth-2 TC0 can be learned using a membership oracle. I wouldn't be totally surprised if the answer is yes. On the other hand, I doubt that $O(1)$-depth TC0 can be learned with membership queries. It might be good to start with AC0[6] (or even AC0[2]) and go from there.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.