Abstract
The proper learning problem for a circuit class C is the following: given oracle access to a function f(x), find a minimal sized circuit T in C computing f. This problem, also known as the reconstruction problem for C, is known to be hard even for very simple classes of circuits in both the Boolean and Arithmetic settings. For arithmetic circuit classes C where we have some understanding in the form of lower bounds, can we exploit this understanding to design proper learning algorithms for C? We give such proper learning algorithms for some subclasses of arithmetic circuits. However, our algorithms are not worst case but they succeed provided that the unknown circuit T satisfies certain non-degeneracy conditions that are satisfied for example if T is not very large and the field constants in T are chosen randomly. Based on joint work with Chandan Saha.