Nyström方法已被广泛用于提高批核学习的计算效率。 Nyström方法的关键思想是从T个训练实例的集合中随机采样M个支持向量,并在由随机采样的支持向量跨越的空间中学习核分类器。 在这项工作中,我们研究了使用Nyström方法进行的在线正则化内核学习,重点是样本复杂度,即产生最佳收敛速度O(1 / T)所需的随机采样支持向量的数量,其中T为在线学习中收到的培训实例的数量。 我们证明,当损失函数为光滑且强凸时,仅 需要随机采样的支持向量来保证O(logT / T)收敛速度,除了 因素。 我们通过广泛的实证研究进一步验证了我们的理论。