标题： 大边缘学习的依赖分布的样本复杂度 显示英文标题

标题： Distribution-Dependent Sample Complexity of Large Margin Learning

摘要： 我们获得了大间隔分类与L2正则化样本复杂度的分布特定刻画：我们引入了“间隔适应维度”，这是一个仅依赖于数据分布二阶统计量的简单函数，并且展示了分布特定的样本复杂度上下界，这两个界都由数据分布的间隔适应维度决定。 上界是普适的，而下界对于具有独立特征的子高斯分布族成立。 我们得出结论，这个新的量紧密刻画了大间隔分类的真实样本复杂度。 为了证明下界，我们开发了若干个独立感兴趣的全新工具。 这些包括打散与学习难度之间新的联系，线性分类器打散的新性质，以及由子高斯变量生成的随机Gram矩阵最小特征值的一个新下界。 我们的结果可以用于定量比较大间隔学习与其他学习规则，并改进使用样本复杂度界的技巧，例如主动学习方法的有效性。 显示英文摘要

摘要： We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the margin-adapted dimension of the data distribution. The upper bounds are universal, and the lower bounds hold for the rich family of sub-Gaussian distributions with independent features. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. To prove the lower bound, we develop several new tools of independent interest. These include new connections between shattering and hardness of learning, new properties of shattering with linear classifiers, and a new lower bound on the smallest eigenvalue of a random Gram matrix generated by sub-Gaussian variables. Our results can be used to quantitatively compare large margin learning to other learning rules, and to improve the effectiveness of methods that use sample complexity bounds, such as active learning.