How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions

Tao Lin

While many classical notions of learnability (e.g., PAC learnability) are distribution-free, utilizing the specific structures of an input distribution may improve learning perform…