Spectral k-Support Norm Regularization

Andrew M. McDonald, Massimiliano Pontil, Dimitris StamosNeurIPS 2014

This paper presents a significant advancement in how we regularize matrices to find low-rank structures. By extending the $k$-support norm from vectors to matrices, the authors provide a more flexible and powerful alternative to the ubiquitous trace norm.

TL;DR

The authors introduce the spectral $k$-support norm, a novel matrix regularizer that outperforms the standard trace norm in matrix completion tasks. They provide a unified framework called "box-norms" that links this new norm to multitask learning and deliver a highly efficient $O(d \log d)$ algorithm for its computation.

What Problem Does This Paper Address?

In fields like collaborative filtering (e.g., predicting movie ratings), we often need to recover a "low-rank" matrix from just a few observed entries. The standard tool for this is trace norm regularization (the sum of singular values).

However, the trace norm can be a blunt instrument. While it encourages low rank, it doesn't always capture the nuances of the underlying data structure as effectively as we'd like. The authors look to the $k$-support norm—which has shown great success in sparse vector prediction—and ask: Can we extend this to matrices, and can we do it efficiently enough for large-scale problems?

Methods

The paper's technical core revolves around three main contributions:

  1. The Box-Norm Framework: The authors define a new class of norms called "box-norms," which are defined as a parameterized infimum of quadratics. They prove that the $k$-support norm is a specific case of this family.
  2. Spectral Extension: Using a classical result by von Neumann, they extend these vector box-norms to matrices. By applying the norm to the vector of a matrix's singular values, they create orthogonally invariant matrix norms. This results in the "spectral $k$-support norm."
  3. The $O(d \log d)$ Algorithm: Computing these norms usually involves complex optimization. The authors derive a fast algorithm for the proximity operator (a key component in first-order optimization methods like FISTA). By using a Lagrangian formulation and a clever binary search/linear interpolation approach, they reduce the complexity to $O(d \log d)$, significantly faster than previous methods.

Key Insights and Ideas

  • Bridging the Gap: The spectral $k$-support norm acts as a "middle ground." While the trace norm is the convex hull of rank-1 matrices, the spectral $k$-support norm is the convex hull of matrices with rank at most $k$. This allows for a more refined control over the rank of the solution.
  • The Cluster Norm Connection: One of the most interesting theoretical "aha" moments is the discovery that the cluster norm (used in multitask learning) is actually a spectral box-norm. This provides a new interpretation of the cluster norm as a "perturbed" version of the $k$-support norm.
  • Parameter $a$ as a Noise Buffer: In the box-norm formulation, the parameter $a$ regulates a small $\ell_2$ component. The experiments show that when $a > 0$, the norm handles noisy data better than the "pure" $k$-support norm (where $a=0$).
Parameter a vs SNR

Key Results

  • Computational Speedup: On a vector of size 32,000, the authors' new algorithm took 0.0181 seconds, compared to 35.6 seconds for the previous state-of-the-art method. This is a massive leap for practical applications.
  • State-of-the-Art Accuracy: In matrix completion tests, the spectral $k$-support (ks) and box-norms (box) consistently achieved lower test errors than both the trace norm (tr) and the matrix elastic net (en) across all datasets (MovieLens and Jester).
Test Error Comparison
  • Rank Recovery: When combined with a final "hard-thresholding" step, the proposed norms were highly effective at recovering the true rank of noiseless matrices.

Limitations and Future Work

  • Hyperparameter Tuning: The spectral $k$-support norm introduces an additional parameter ($k$) that must be tuned via cross-validation. The box-norm adds even more (parameters $a$ and $c$), which increases the search space during model selection.
  • Hard Thresholding: The authors noted that they often needed a final hard-thresholding step to reach the exact target rank, suggesting that while the norm encourages low rank, it might not always produce a "clean" low-rank cut-off on its own.
  • Future Directions: The authors suggest exploring the application of these norms to clustering problems in multitask learning and developing tighter theoretical bounds (Rademacher complexities) for these norm families.

Summary updated

BibTeX
@inproceedings{mcdonald2014spectral,
  author = {Andrew M. McDonald and Massimiliano Pontil and Dimitris Stamos},
  title = {{Spectral k-Support Norm Regularization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure