<p>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.</p>

<p>However, parities and noisy parities <em>can</em> 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.</p>

CC BY-SA 3.0
2014-04-08T02:51:02.873Z
2014-04-08T04:21:22.920Z
2014-04-08T04:21:22.920Z
greg
<p>The main thing missing from your list is the <a href="https://www.cs.utexas.edu/~klivans/crypto-hs.pdf">beautiful 2006 paper of Klivans and Sherstov</a>.  They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.</p>

CC BY-SA 3.0
2018-02-18T08:51:14.100Z
What is the fastest running time known for learning such LTF circuits? (or anything inside $TC^0$)
gradstudent
CC BY-SA 3.0
2014-04-08T15:30:18.423Z
2014-04-08T15:30:18.423Z
Scott Aaronson
<p>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. </p>

<p>What I've discovered thus far is:</p>

<ul>
<li>All of  $\mathsf{AC}^0$ can be learned in quasipolynomial time under the uniform distribution via <a href="http://www.cs.columbia.edu/~rocco/Teaching/S12/Readings/LMN.pdf" rel="nofollow">Linial-Mansour-Nisan</a>. </li>
<li>Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of <a href="http://dl.acm.org/citation.cfm?id=972643" rel="nofollow">Naor-Reingold</a> that $\mathsf{TC}^0$ admits PRFGs, suggests that $\mathsf{TC}^0$ represents the limits of learnability (at least in a PAC-sense)</li>
<li>There's a 2002 paper by <a href="http://www.stat.ucla.edu/~cocteau/dimacs/servedio.pdf" rel="nofollow">Jackson/Klivans/Servedio</a> that can learn a fragment of $\mathsf{TC}^0$ (with at most polylogarithmic majority gates). </li>
</ul>

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

<blockquote>
  <p>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 ? </p>
</blockquote>

CC BY-SA 3.0
2014-04-04T00:52:14.007Z
+1 Nice question. Didn't Lance have a related blog post some time ago?
Kaveh
CC BY-SA 3.0
2014-04-04T01:38:45.640Z
Do you mean this one (guest post by Ryan O'Donnell): http://blog.computationalcomplexity.org/2005/08/depth-two-tc0-by-ryan-odonnell.html
Suresh Venkat
CC BY-SA 3.0
2014-04-04T01:46:55.053Z
I feel there was something more recent where he talked about machine learning and multiplication (which is complete for TC0) but I can't find it.
Kaveh
CC BY-SA 3.0
2014-04-04T01:49:43.547Z
Maybe this one: http://blog.computationalcomplexity.org/2013/08/why-is-multiplication-hard.html
Suresh Venkat
CC BY-SA 3.0
2014-04-08T01:35:22.280Z
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.
Robin Kothari
<cc.complexity-theory><reference-request><cr.crypto-security><lg.learning><boolean-functions>
On the status of learnability inside $\mathsf{TC}^0$
Suresh Venkat
# On the status of learnability inside $\mathsf{TC}^0$

(Asked by: username_0 on 2014-04-03)

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](http://www.cs.columbia.edu/~rocco/Teaching/S12/Readings/LMN.pdf).
* Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of [Naor-Reingold](http://dl.acm.org/citation.cfm?id=972643) 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](http://www.stat.ucla.edu/~cocteau/dimacs/servedio.pdf) 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 ?

**Tags:** cc.complexity-theory, reference-request, cr.crypto-security, lg.learning, boolean-functions
> **Comments:**
> **username_1**: +1 Nice question. Didn't Lance have a related blog post some time ago?  
> **username_0**: Do you mean this one (guest post by Ryan O'Donnell): http://blog.computationalcomplexity.org/2005/08/depth-two-tc0-by-ryan-odonnell.html  
> **username_1**: I feel there was something more recent where he talked about machine learning and multiplication (which is complete for TC0) but I can't find it.  
> **username_0**: Maybe this one: http://blog.computationalcomplexity.org/2013/08/why-is-multiplication-hard.html  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_4 on 2014-04-08. Score: 9 | Accepted answer

The main thing missing from your list is the [beautiful 2006 paper of Klivans and Sherstov](https://www.cs.utexas.edu/~klivans/crypto-hs.pdf). They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.

> **Comments:**
> **username_5**: What is the fastest running time known for learning such LTF circuits? (or anything inside $TC^0$)  

---

### Answer by username_3 on 2014-04-08. Score: 5

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.


---

