Group：Student Seminar
Title：Learning Sparse Functions
Speaker： Wen Yuan University
Time： 2010-12-09 16:00-2010-12-09 17:00
Venue：FIT 1-222

Abstract:

In this talk, I will describe a learning algorithm that learns the target function by finding a sparse function. The main advantage of the algorithm is that its running time is polynomial in the number of non-zero coefficients. However, the disadvantage is that the algorithm uses the query model.

I will first show that, if function f can be approximated by a polynomial sparse function g, then it can be approximated by a polynomial sparse function that has only "significant" coefficients. Then I will show a randomized polynomial time procedure that given a function f and a threshold \theta outputs (w.p. 1-\delta) all the coefficients for which |^f(z)|>=\theta. And the procedure runs in polynomial time in n, 1/\theta and \log(1/\delta).

Short Bio: