  Optimal margin Distribution Machine (ODM) is a newly proposed statistical
learning framework rooting in the novel margin theory, which demonstrates
better generalization performance than the traditional large margin based
counterparts. Nonetheless, it suffers from the ubiquitous scalability problem
regarding both computation time and memory as other kernel methods. This paper
proposes a scalable ODM, which can achieve nearly ten times speedup compared to
the original ODM training method. For nonlinear kernels, we propose a novel
distribution-aware partition method to make the local ODM trained on each
partition be close and converge fast to the global one. When linear kernel is
applied, we extend a communication efficient SVRG method to accelerate the
training further. Extensive empirical studies validate that our proposed method
is highly computational efficient and almost never worsen the generalization.
