1

This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean function into a learning algorithm.

Have there been other works in this line? What are the most recent things we know about such conversion from approximate degree to learning algorithms?

gradstudent
  • 1,453
  • 8
  • 12
  • 2
    This survey by L. Hellerstein and R. Servedio covers more examples of learning algorithms using the same strategy. – Robin Kothari Feb 13 '18 at 18:02
  • See also this survey by de Wolf (esp. Section 3.3). – Clement C. Feb 13 '18 at 18:09
  • Thanks! (@ClementC. I dont see any bounding of the approximate degree going on in your reference. What am I missing?) – gradstudent Feb 13 '18 at 21:38
  • You're probably not missing anything; I must have. – Clement C. Feb 13 '18 at 21:40
  • Thanks! Let me just use this discussion thread to ask a related thing : So approximate degree of Majority seems to be $\Omega(n)$ and hence that implies that LTF circuits can never have a small approximate degree. Right? So does that also mean that there cant be fast learning algorithms for LTF circuit classes? What is the best we know of about this for this specific case? – gradstudent Feb 15 '18 at 02:13
  • @gradstudent Not sure I understand your question. Are you asking if the class of Boolean functions which can be represented by halfspaces is efficiently PAC-learnable? (If so, yes, this follows from a VC dimension argument) – Clement C. Feb 18 '18 at 03:57
  • I am talking of any class of functions which is representable by some LTF circuits. Say "all Boolean functions representable by size s depth 2 LTF circuits" for some s. (...not sure why you thought of half-spaces..) – gradstudent Feb 18 '18 at 05:31
  • @gradstudent because the terms LTFs (Linear Threshold Functions) and halfspaces are synonymous (cf. e.g. Section 3 of these lecture notes), and I was not familiar with the use of "LTF circuit" for circuit with threshold gates. – Clement C. Feb 18 '18 at 05:51
  • 1
    Now, again based on your last comment, this seems relevant: https://cstheory.stackexchange.com/questions/21916/on-the-status-of-learnability-inside-mathsftc0 – Clement C. Feb 18 '18 at 05:55
  • That discussion does seem close to what I am looking for. But I dont see any references shared there about fastest running times for learning this class $TC^0$. Any? – gradstudent Feb 18 '18 at 09:01

0 Answers0