  Embedding methods for mixed-curvature spaces are powerful techniques for
low-distortion and low-dimensional representation of complex data structures.
Nevertheless, little is known regarding downstream learning and optimization in
the embedding space. Here, we address for the first time the problem of linear
classification in a product space form -- a mix of Euclidean, spherical, and
hyperbolic spaces with different dimensions. First, we revisit the definition
of a linear classifier on a Riemannian manifold by using geodesics and
Riemannian metrics which generalize the notions of straight lines and inner
products in vector spaces, respectively. Second, we prove that linear
classifiers in $d$-dimensional constant curvature spaces can shatter exactly
$d+1$ points: Hence, Euclidean, hyperbolic and spherical classifiers have the
same expressive power. Third, we formalize linear classifiers in product space
forms, describe a novel perceptron classification algorithm, and establish
rigorous convergence results. We support our theoretical findings with
simulation results on several datasets, including synthetic data, MNIST and
Omniglot. Our results reveal that learning methods applied to small-dimensional
embeddings in product space forms significantly outperform their algorithmic
counterparts in Euclidean spaces.
