CAREER: Algorithmic Aspects of Machine Learning

职业：机器学习的算法方面

• 批准号: 1453261
• 负责人: Ankur Moitra
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1453261&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Aspects; Machine; Learning

Algorithms and complexity are the theoretical foundation and backbone of machine learning. Yet over the past few decades an uncomfortable truth has set in that worst-case analysis is not the right framework to study it: every model that is interesting enough to use in practice leads to computationally hard problems. The goal of the PI's research agenda is to move beyond worst-case analysis. This involves formalizing when and why heuristics -- such as alternating minimization and Gibbs sampling -- work as well as designing fundamentally new algorithms for some of the basic tasks in machine learning. This project has already had a number of successes such as provable algorithms for nonnegative matrix factorization, topic modeling and learning mixture models.The PI will investigate several new directions in topics such as sparse coding, inference in graphical models, inverse problems for tensors, and semi-random models. These projects will leverage a wide range of modern tools to give new provable algorithms in each of these settings, and will involve making new connections between alternating minimization and approximate gradient descent, analyzing Gibbs sampling through correlation decay and coupling, connecting tensor completion and quantum complexity and rethinking the standard distributional models used in machine learning. These projects cut across several areas of computer science and applied mathematics and will build new bridges between them, as well as expanding the reach of theory into a number of domains where there is a serious gap in our current understanding. Bridging theory and practice has significant broader impact. The PI will continue to mentor undergraduate and graduate students.

算法和复杂性是机器学习的理论基础和支柱。然而，在过去的几十年里，一个令人不安的事实是，最坏情况分析并不是研究它的正确框架：每个足够有趣的模型在实践中都会导致计算困难的问题。 PI 研究议程的目标是超越最坏情况分析。这涉及到形式化启发式算法（例如交替最小化和吉布斯采样）起作用的时间和原因，以及为机器学习中的一些基本任务设计全新的算法。该项目已经取得了许多成功，例如可证明的非负矩阵分解算法、主题建模和学习混合模型。PI 将研究稀疏编码、图模型推理、张量逆问题和学习混合模型等主题的几个新方向。半随机模型。这些项目将利用广泛的现代工具在每种设置中提供新的可证明算法，并将涉及在交替最小化和近似梯度下降之间建立新的联系，通过相关衰减和耦合分析吉布斯采样，连接张量完成和量子复杂性并重新思考机器学习中使用的标准分布模型。这些项目跨越了计算机科学和应用数学的多个领域，并将在它们之间建立新的桥梁，并将理论的范围扩展到我们目前理解上存在严重差距的许多领域。连接理论和实践具有更广泛的影响。 PI 将继续指导本科生和研究生。