Variational functions of Gram matrices: convex optimization and applications

We propose a class of convex penalty functions called Variational Gram Functions, that can promote pairwise relations, such as orthogonality, among a set of vectors in a vector space. When used as regularizers in convex optimization problems, these functions of a Gram matrix find application in hierarchical classification, multitask learning, and estimation of vectors with disjoint supports, among other applications. We describe a general condition for convexity, which is then used to prove the convexity of a few known functions as well as new ones. We give a characterization of the associated subdifferential and the proximal operator, and discuss efficient optimization algorithms for loss-minimization problems regularized with these penalty functions. Numerical experiments on a hierarchical classification problem are presented, demonstrating the effectiveness of these penalties and the associated optimization algorithms in practice.

(Based on joint work with Amin Jalali and Lin Xiao.)