Variational Gram Functions: Convex Analysis and Optimization
  We propose a new class of convex penalty functions, called \emph{variational
Gram functions} (VGFs), that can promote pairwise relations, such as
orthogonality, among a set of vectors in a vector space. These functions can
serve as regularizers in convex optimization problems arising from hierarchical
classification, multitask learning, and estimating vectors with disjoint
supports, among other applications. We study convexity for VGFs, and give
efficient characterizations for their convex conjugates, subdifferentials, and
proximal operators. We discuss efficient optimization algorithms for
regularized loss minimization problems where the loss admits a common, yet
simple, variational representation and the regularizer is a VGF. These
algorithms enjoy a simple kernel trick, an efficient line search, as well as
computational advantages over first order methods based on the subdifferential
or proximal maps. We also establish a general representer theorem for such
learning problems. Lastly, numerical experiments on a hierarchical
classification problem are presented to demonstrate the effectiveness of VGFs
and the associated optimization algorithms.
