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.