Large-Scale Minimal Complexity Machines Using Explicit Feature Maps
提出一种随机次梯度下降求解器，用显式特征映射近似核函数，使最小复杂度机器能高效处理大规模数据集，比支持向量机更稀疏。
Minimal complexity machines (MCMs) are a class of hyperplane classifiers that try to minimize a tight bound on the Vapnik-Chervonenkis dimension. MCMs can be used both in the input space and in a higher dimensional feature space via the kernel trick. MCMs tend to produce very sparse solutions in comparison to support vector machines, often using three to ten times fewer support vectors. However, large datasets present significant challenges in terms of storage and operations on the kernel matrix. In this paper, we present a stochastic subgradient descent solver for large-scale machine learning with the MCM. The proposed approach uses an explicit feature map-based approximation of the kernel, to improve the scalability of the algorithm.