支持向量机(Support Vector Machines,SVM)与惩罚逻辑斯蒂回归(Penalty Logistic Regression,PLR)是机器学习中两种重要的核学习方法,具有完善的理论基础。对于原始空间中的线性不可分问题,SVM和PLR都可以通过核方法将数据映射至高维线性可分的空间中进行分类。在这种情况下,其对应线性模型的性能远不如非线性模型。然而,非线性核学习问题的计算时间复杂度理论上不会低于O n~2,其中n为训练样本的规模。这使得非线性SVM和PLR的应用难以扩展至大规模数据集。为此,本文分别设计非线性SVM的两种亚线性时间优化算法和PLR的一种亚线性时间优化算法。首先,基于梯度下降的优化方法设计非线性SVM的亚线性优化算法。算法的每次迭代包括一个梯度下降更新步和一个投影步。在算法的每次迭代过程中应用随机傅里叶特征映射将采样得到的样本映射至随机傅里叶特征空间执行上述步骤,使得算法单次迭代的时间复杂度为常数。推导出算法的收敛率,并证明算法返回对应目标优化问题ε近似解的时间复杂度是独立于样本规模的。进一步,将SVM中的损失函数替换为指数损失函数,可基于相同的方法设计非线性PLR的亚线性优化算法。然后,基于子集选择技术,结合改进的原始-对偶优化算法,设计非线性SVM的另一种亚线性优化算法。理论上证明对应算法求解SVM的时间复杂度是独立于样本规模的。最后,在多个标准的大规模数据集上设计对比实验,表明所提出算法的高效性和有效性。