Parallelized Tensor Train Learning of Polynomial Classifiers
  In pattern classification, polynomial classifiers are well-studied methods as
they are capable of generating complex decision surfaces. Unfortunately, the
use of multivariate polynomials is limited to kernels as in support vector
machines, because polynomials quickly become impractical for high-dimensional
problems. In this paper, we effectively overcome the curse of dimensionality by
employing the tensor train format to represent a polynomial classifier. Based
on the structure of tensor trains, two learning algorithms are proposed which
involve solving different optimization problems of low computational
complexity. Furthermore, we show how both regularization to prevent overfitting
and parallelization, which enables the use of large training sets, are
incorporated into these methods. Both the efficiency and efficacy of our
tensor-based polynomial classifier are then demonstrated on the two popular
datasets USPS and MNIST.
