讨论组:学生讲座
标题:Learning Submodular Function
演讲人: 胡巍
时间: 2011-03-24 16:30-2011-03-24 17:30
地点:FIT 1-222

内容:

Let f be a function from 2^[n] to \mathcal{R}. If for all S, T\subseteq [n], f(S) + f(T) >= f(S\cap T) + f(S\cup T), f is submodular. Non-negative monotone subumodular function can be approximated with factor O(\sqrt{n}\log{n})[Geomans 09]. [Balcan, Harvey 11] shows that such a function can be PMAC-learned with a factor O(\sqrt{n+1}) where they modify the PAC model to PMAC model. Using their model, they show an low-bound of O((n+1)^{1/3}/\log{n}). In this student seminar, I will present their proof of the first part. That is, non-negative monotone submodular function can be PMAC-learned with a factor of O(\sqrt{n+1}).