RI: AF: Medium: Learning and Matrix Reconstruction with the Max-Norm and Related Factorization Norms

矩阵学习是许多学习问题的基础。这些问题包括可以直接表述为学习一些未知矩阵的问题，以及涉及参数矩阵的更广泛的学习问题。最直接的矩阵学习问题是矩阵补全，补全部分观察到的矩阵中不可见的项。矩阵补全最近在协同过滤的实践中（特别是通过Netflix挑战）和作为压缩感知扩展的理论分析中受到了很多关注。矩阵学习也被用于聚类、迁移和多任务学习以及相似学习。近年来，矩阵学习的主要方法，特别是在矩阵补全的背景下，使用了矩阵跟踪范数（部分由该奖项的PI开发）。实际上，基于跟踪规范的方法在各种应用程序中都取得了很大的成功。本课题开发并研究了迹范数的替代矩阵范数，其中最重要的是有前途的极大范数。使用最大规范学习最初是在2004年提出的（与跟踪规范一起），但没有得到同样的关注，尽管有许多理论和实证优势。该项目确定了最大规范和相关规范可能有益的领域，开发了使用这些规范的计算方法，并促进了这些规范的采用。一个中心目标是开发最大范数正则化问题的优化方法，使其与跟踪范数正则化问题的相应方法（如奇异值阈值和lr型方法）一样有效。除了矩阵补全之外，该项目还将最大范数应用于以前应用过跟踪范数的问题，以及新的设置。新的应用包括聚类、二进制哈希、众包、人口建模排名和相似性学习。该项目下的研究将机器学习和计算理论研究社区联系起来（近年来，与最大范数基本对应的SDP松弛在其中发挥了重要作用）。该项目在社区之间架起了桥梁，部分是通过跨学科教程实现的。通过与社会学家的合作，ppi接触到社会科学，并通过以一种平易近人和可用的方式向受众展示工作，从而增加工作的广泛影响。

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.