| Title | : | Learning Algorithms for Sparsely Oriented Circuits |
| Speaker | : | Sajin Koroth (IIT Madras) |
| Details | : | Tue, Feb 21, 2017 4:00 PM, @ Meeting Room 1 |
| Abstract | : | In this talk we look into learning functions which are computed by circuits whose non-monotonicity is limited. The main objective in learning given blackbox access to a function f from a specific family of functions, is to come with a hypothesis h which agrees with f on an epsilon fraction of inputs, with minimal number of queries. Bshouty and Tamon (1996) came up with a learning algorithm for learning family of monotone functions based on the low-degree learning algorithm of Linial, Mansour and Nisan (1993). A function is said to be monotone if if it is computed by a monotone circuit, i.e, circuits without negations. The natural next step is to study learning problems for non-monotone circuits. A well studied notion of non-monotonicity is to limit the number of negation gates allowed in the circuit computing f.
In this talk, we would first see a learning algorithm of Blais et. al (2014) which established a learning algorithm for functions computed by limited non-monotone circuits where the non-monotonicity is parameterized by the number of negations in the circuit. We then show how to obtain a learning algorithm for functions computed by limited non-monotone circuits where the non-monotonicity is parametrized with a new parameter called orientation. We will recall a characterization of minimal orientation of a function proved by Koroth and Sarma (2014) and then use this characterization to obtain a learning algorithm from the learning algorithm of Blais et. al. On the lower bounds front, we will outline a bound obtained by Blais et al (2014) matching their learning algorithm. We will also see the intuition behind their lower bound strategy, which is based on hardness amplification developed by Feldman et. al (2011) using a specific Fourier analytic property of Boolean functions called noise sensitivity . Based on this intuition and our characterization of orientation we outline a strategy for obtaining learning lower bounds for functions of limited orientation. We then show some major hurdles in implementing our strategy. |