PAC Learning中的大O记号问题

在PAC的框架中所要求的多项式数量样本，其实是Sample Complexity的最坏情况，即上界。可以这么理解：在PAC的定义中的「对任意$m\ge poly(1/ϵ,1/\delta ,n,size(c)$」只是说明样本数量足够大的时候，能将错误缩小到任意范围，但是因为推导过程中有放缩，实际上所需要的样本数量应该是小于等于$poly(1/ϵ,1/\delta ,n,size(c)$的，换言之后者是上界。

所以这里表示Sample Complexity时用大O记号，写作$O(poly(1/ϵ,1/\delta ,n,size(c))$

---

Related

• PAC Learning