Matrix learning is fundamental in many learning problems. These include problems that can be directly formulated as learning some unknown matrix, as well as a broader class of learning problems involving a matrix of parameters. The most direct matrix learning problem is matrix completion, completing unseen entries in a partially observed matrix. Matrix completion has recently received much attention both in practice in collaborative filtering (notably through the Netflix challenge), and theoretical analysis as an extension to compressed sensing. Matrix learning has also been used for clustering, transfer and multi-task learning, and similarity learning.
The dominant approach to matrix learning in recent years, especially in the context of matrix completion, has used the matrix trace norm (developed in part by the PI on this award). Indeed, trace norm-based methods enjoy much success in a variety of applications. This project develops and studies alternative matrix norms to the trace-norm, most importantly the promising max-norm.
Learning with the max-norm was initially presented in 2004 (along with the trace norm), but has not received the same attention, despite many theoretical and empirical advantages. This project identifies domains where the max-norm and related norms can be beneficial, develops computational methods for using these norms, and promotes the adoption of these norms. A central aim is to develop optimization methods for max-norm regularized problems that are as efficient as the corresponding methods for trace-norm regularized problems, such as singular value thresholding and LR-type methods. Beyond matrix completion, the project applies the max-norm both to problems where the trace-norm has been previously applied, and in novel settings. Novel applications include clustering, binary hashing, crowdsourcing, modeling rankings by a population, and similarity learning.
Research under this project links the machine learning and theory-of-computation research communities (where SDP relaxations essentially corresponding to the max-norm have played a significant role in recent years). The project forms bridges between the communities, enabled in part by cross-disciplinary tutorials. Through collaboration with sociologists the PIs reach out to the social sciences, and increase the broad impact of the work by presenting it in an approachable and useable way to this audience.
