讨论组:学生讲座
标题:Learning Sparse Functions
演讲人: 袁文 University
时间: 2010-12-09 16:00-2010-12-09 17:00
地点:FIT 1-222

内容:

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).



人物介绍: