# New Perspectives on k-Support and Cluster Norms

arXiv: https://arxiv.org/abs/1512.08204 · HTML: https://mlsanity.com/paper/1512.08204/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2015.

## Built on by (most cited first, 9 of 9)

- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Conditional Meta-Learning of Linear Representations](https://mlsanity.com/paper/2103.16277/) (2021)
- [Learning Tensor Representations for Meta-Learning](https://mlsanity.com/paper/2201.07348/) (2022)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Decoding Working-Memory Load During n-Back Task Performance from High Channel NIRS Data](https://mlsanity.com/paper/2312.07546/) (2023)
- [Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery](https://mlsanity.com/paper/2401.05394/) (2023)
- [Adaptive Multi-task Learning for Multi-sector Portfolio Optimization](https://mlsanity.com/paper/2507.16433/) (2025)

## Abstract (arXiv)

We study a regularizer which is defined as a parameterized infimum of quadratics, and which we call the box-norm. We show that the k-support norm, a regularizer proposed by [Argyriou et al, 2012] for sparse vector prediction problems, belongs to this family, and the box-norm can be generated as a perturbation of the former. We derive an improved algorithm to compute the proximity operator of the squared box-norm, and we provide a method to compute the norm. We extend the norms to matrices, introducing the spectral k-support norm and spectral box-norm. We note that the spectral box-norm is essentially equivalent to the cluster norm, a multitask learning regularizer introduced by [Jacob et al. 2009a], and which in turn can be interpreted as a perturbation of the spectral k-support norm. Centering the norm is important for multitask learning and we also provide a method to use centered versions of the norms as regularizers. Numerical experiments indicate that the spectral k-support and box-norms and their centered variants provide state of the art performance in matrix completion and multitask learning problems respectively.