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

RI：AF：中：使用最大范数和相关因式分解范数进行学习和矩阵重建

基本信息

批准号：
1302662
负责人：
Nathan Srebro
金额：
$ 90万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2013
资助国家：
美国
起止时间：
2013-06-01 至 2019-03-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1302662&HistoricalAwards=false
关键词：
RI AF Medium Learning Matrix

项目摘要

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.

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

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Implicit Regularization in Matrix Factorization

DOI：
10.1109/ita.2018.8503198
发表时间：
2017-05
期刊：
2018 Information Theory and Applications Workshop (ITA)
影响因子：
0
作者：
Suriya Gunasekar;Blake E. Woodworth;Srinadh Bhojanapalli;Behnam Neyshabur;N. Srebro
通讯作者：
Suriya Gunasekar;Blake E. Woodworth;Srinadh Bhojanapalli;Behnam Neyshabur;N. Srebro

Global Optimality of Local Search for Low Rank Matrix Recovery