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: