On the status of learnability inside $\mathsf{TC}^0$

Question

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 ?

Answer 1

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.

Answer 2

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.