New Perspectives on k-Support and Cluster Norms
This work addresses the computational bottleneck for applying k-support and cluster norms in machine learning tasks like matrix completion and multitask learning, offering an incremental improvement with practical benefits.
The paper tackled the problem of efficiently computing the proximity operator for k-support and cluster norms, which are used in sparse vector and matrix prediction problems, by deriving a new algorithm that improves upon the standard method and applying it to matrix completion and multitask learning datasets, resulting in state-of-the-art performance that significantly outperforms trace norm and elastic net penalties.
The $k$-support norm is a regularizer which has been successfully applied to sparse vector prediction problems. We show that it belongs to a general class of norms which can be formulated as a parameterized infimum over quadratics. We further extend the $k$-support norm to matrices, and we observe that it is a special case of the matrix cluster norm. Using this formulation we derive an efficient algorithm to compute the proximity operator of both norms. This improves upon the standard algorithm for the $k$-support norm and allows us to apply proximal gradient methods to the cluster norm. We also describe how to solve regularization problems which employ centered versions of these norms. Finally, we apply the matrix regularizers to different matrix completion and multitask learning datasets. Our results indicate that the spectral $k$-support norm and the cluster norm give state of the art performance on these problems, significantly outperforming trace norm and elastic net penalties.