AF: Small: Online Algorithms and Approximation Methods in Learning

AF：小：学习中的在线算法和近似方法

基本信息

批准号：
2008688
负责人：
Aditya Bhaskara
金额：
$ 35万
依托单位：
University of Utah
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008688&HistoricalAwards=false
关键词：
AF Small Online Algorithms Approximation

项目摘要

Modern machine-learning applications aim to solve difficult computational problems accurately, quickly and at scale. This has led to significant algorithmic challenges that are compounded by practical considerations like robustness to noise and the distributed nature of data. The goal of the project is to develop a formal understanding of when efficient learning is possible, and to develop novel algorithmic insights. The techniques developed in the project will lead to progress in approximation algorithms, optimization, sublinear algorithms, and computational complexity. The project includes a plan to develop courses that teach undergraduate and graduate students to formally reason about machine-learning systems and to understand their power and limitations. The courses will help train the next generation of the workforce, and will be offered at the University of Utah, with much of the material being publicly accessible.The project aims to address two core questions in reasoning about machine learning. The first one is related to the computational hardness of learning problems. For problems such as sparse coding and learning low-depth neural networks, all the known algorithms require strong structural assumptions in order to obtain learning guarantees. The project will study methods (for these and other problems) that enable one to weaken these assumptions, while obtaining weaker yet practically relevant guarantees. The second question is related to learning in online arrival models, motivated by recommender systems and signal processing. Here, many of the known theoretical results fall short when data is noisy or is only partially observed, and the project will develop formal models and algorithmic results for these settings.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

现代的机器学习应用程序旨在准确，快速，大规模地解决困难的计算问题。这导致了巨大的算法挑战，这些挑战是由稳健性对噪声和数据的分布性质等实际考虑的复杂性。该项目的目的是对何时进行有效学习的正式理解，并开发新颖的算法见解。项目中开发的技术将导致近似算法，优化，sublinear算法和计算复杂性的进展。该项目包括一项计划，以开发教学本科生和研究生的课程，以正式理解机器学习系统并了解其力量和局限性。这些课程将有助于培训下一代劳动力，并将在犹他大学提供，其中许多材料都可以公开访问。该项目旨在解决有关机器学习推理的两个核心问题。第一个与学习问题的计算硬度有关。对于稀疏编码和学习低深度神经网络等问题，所有已知算法都需要强大的结构假设才能获得学习保证。该项目将研究（对于这些问题和其他问题），使人们能够削弱这些假设，同时获得较弱但实际上相关的保证。第二个问题与在线到达模型中的学习有关，这是由推荐系统和信号处理的动机。在这里，当数据嘈杂或仅部分观察到时，许多已知的理论结果都缺乏，并且该项目将针对这些环境开发正式的模型和算法结果。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来支持的。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Online MAP Inference of Determinantal Point Processes

行列式点过程的在线 MAP 推理

DOI：
发表时间：
2020
期刊：
Advances in Neural Information Processing Systems 33 (NeurIPS 2020
影响因子：
0
作者：
Bhaskara, Aditya;Karbasi, Amin;Lattanzi, Silvio;Zadimoghaddam, Morteza
通讯作者：
Zadimoghaddam, Morteza

Principal Component Regression with Semirandom Observations via Matrix Completion

通过矩阵补全进行半随机观测的主成分回归

DOI：
发表时间：
2021
期刊：
International Conference on Artificial Intelligence and Statistics (AISTATS
影响因子：
0
作者：
Bhaskara, A.;Ruwanpathirana, A.;Wijewardena, M.
通讯作者：
Wijewardena, M.

Additive Error Guarantees for Weighted Low Rank Approximation

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
Aditya Bhaskara;Aravinda Kanchana Ruwanpathirana;Pruthuvi Maheshakya Wijewardena
通讯作者：
Aditya Bhaskara;Aravinda Kanchana Ruwanpathirana;Pruthuvi Maheshakya Wijewardena