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将继续指导本科生和研究生。