  Invariance (defined in a general sense) has been one of the most effective
priors for representation learning. Direct factorization of parametric models
is feasible only for a small range of invariances, while regularization
approaches, despite improved generality, lead to nonconvex optimization. In
this work, we develop a convex representation learning algorithm for a variety
of generalized invariances that can be modeled as semi-norms. Novel Euclidean
embeddings are introduced for kernel representers in a semi-inner-product
space, and approximation bounds are established. This allows invariant
representations to be learned efficiently and effectively as confirmed in our
experiments, along with accurate predictions.
