We propose a simple discrete data model inspired from natural data such as texts or images, and use it to study the importance of learning features in order to achieve good generalization. We provide evidence that a learner succeeds if and only if it identifies the correct features, and moreover derive non-asymptotic generalization error bounds that precisely quantify the penalty that one must pay for not learning features.
Copyright. All Rights Reserved.